忘记密码   免费注册 查看新帖 |

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT 徽章 文库 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
12下一页
最近访问板块 发新帖
查看: 1217 | 回复: 11

[学习共享] 用ps递归算法,解扑鱼题,教程。 [复制链接]

论坛徽章:
0
发表于 2017-08-22 13:26 |显示全部楼层

本帖目的:
1 展示ps递归算法,用法。
2 用简单明了的代码,演示扑鱼方法。既然演示为目的,那么就要猪懂傻改,我写的代码即注释。

另外我认为【能看懂的代码才牛x】,而不是【看不懂才牛x】。
这一点,我估计py人会认同。而perl人,awk人则反对。
我想请问,一个老板会愿意招【别人看不懂你代码,世界上只有你懂自己写的代码】这样的人吗?
实际上我想想学【金awk】,【银perl】可惜没好老师,老师只会写天书,这能怪谁呢?

数大的话,有人关注性能吗?
1 谁能帮我优化思路,代码?
2 这是一个典型的,每个任务很小,任务数很多的cpu密集型应用。
2.1win,linux中,ps可以多线程,解这道题。py有线程癌症。
2.2这种应用,不适合用多进程来解。因为进程切换耗时大于任务耗时。除非一次传递一组,几万个任务。
win中ps有多进程并发。linux中暂无。

------------------------------------------------------
递归,简单地说就是函数不停地调用自身。
循环和递归,是程序常用解题方式,几乎99%的语言都有。
递归使写程序更简单,更清晰,但比循环更占内存。

从编写脚本来说,99。9%的人都用循环,0。1%的人用递归。
或许循环更容易理解,性能更好?
好象我平常也喜欢循环。

问:那么如何从递归中退出呢?
答:一般建议在递归中放上if或else。也就是说在递归里面先判断条件。条件成立,或者不成立,再无限递归。

问:powershell递归如何增强性能?
答:
尽量使用强类型对象。

------------------------------------------------------
问题描述
A、B、C、D、E这5个人合伙夜间捕鱼,凌晨时都已经疲惫不堪,于是各自在河边的树丛中找地方睡着了。
第二天日上三竿时,
A第一个醒来,他将鱼平分为5份,把多余的一条扔回河中,然后拿着自己的一份回家去了;
B第二个醒来,但不知道A已经拿走了一份鱼,于是他将剩下的鱼平分为5份,扔掉多余的一条,然后只拿走了自己的一份;
接着C、D、E依次醒来,也都按同样的办法分鱼。
问这5人至少合伙捕到多少条鱼?每个人醒来后所看到的鱼是多少条?

------------------------------------------------------
  1. #
  2. function 判断数字是否含有小数部分([decimal]$输入)
  3. {
  4.         if ( ($输入 - [system.math]::Floor($输入)) -ne 0)
  5.         {
  6.                 return $true
  7.         }
  8.         else
  9.         {
  10.                 return $false
  11.         }
  12. }

  13. function 递归求鱼([decimal]$传入数)
  14. {
  15.         if (判断数字是否含有小数部分 $传入数)
  16.         {
  17.                 return
  18.         }
  19.         else
  20.         {
  21.                 if ($script:当前人 -eq 2)
  22.                 {
  23.                         $script:e = $传入数
  24.                 }

  25.                 if ($script:当前人 -eq 3)
  26.                 {
  27.                         $script:d = $传入数
  28.                 }

  29.                 if ($script:当前人 -eq 4)
  30.                 {
  31.                         $script:c = $传入数
  32.                 }

  33.                 if ($script:当前人 -eq 5)
  34.                 {
  35.                         $script:b = $传入数
  36.                 }

  37.                 if ($script:当前人 -ge $script:扑鱼达人总数)
  38.                 {
  39.                         $输出 =
  40. @"
  41. 1  $传入数
  42. 2  $script:b
  43. 3  $script:c
  44. 4  $script:d
  45. 5  $script:e
  46. ----------------
  47. "@
  48.                         Write-Host $输出
  49.                 }
  50.                 else
  51.                 {
  52.                         $script:当前人++
  53.                         return ( 递归求鱼 ($传入数 * 5 / 4 + 1) )
  54.                 }
  55.         }
  56. }

  57. $script:扑鱼达人总数 = 6
  58. foreach ($i in 6..2000)
  59. {
  60.         $script:当前人 = 1 #从最后1人,倒推 5+1 次
  61.         递归求鱼 $i
  62. }

  63. <#
  64. 返回:
  65. 1  3121
  66. 2  2496
  67. 3  1996
  68. 4  1596
  69. 5  1276
  70. ----------------
  71. #>
复制代码


------------------------------------------------------

powershell脚本第一课:面向对象简介1
http://bbs.chinaunix.net/thread-4263988-1-1.html

ps第二课:常用对象类型
http://bbs.chinaunix.net/thread-4264061-1-1.html

ps第三课:面向对象语言有啥优缺点?
http://bbs.chinaunix.net/thread-4264062-1-1.html

ps第4课:文件目录对象介绍
http://bbs.chinaunix.net/thread-4264293-1-1.html

ps第5课:常用帮助命令
http://bbs.chinaunix.net/thread-4264294-1-1.html

ps第6课:单个字符对象,讲ps如何处理单个字符,含汉字
http://bbs.chinaunix.net/thread-4264556-1-3.html

ps第7课:powershell到底有何优势,为什么要学?
http://bbs.chinaunix.net/thread-4264776-1-1.html

ps第8课:用powershell读写文本、二进制文件。
http://bbs.chinaunix.net/thread-4266404-1-1.html
--------------------------------------------------------
字符界面版,powershell2048游戏。win_linux_通用
http://bbs.chinaunix.net/thread-4260709-1-1.html

http://bbs.chinaunix.net/thread-4266193-1-1.html
跨平台ps命令行游戏:《抽一张扑克牌比大小.ps1》




论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-08-22 16:15 |显示全部楼层
牛x!!
看不懂
老中医
10人合伙捕鱼 time多少?
每个人醒来后所看到的鱼是多少条?

论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-08-22 16:22 |显示全部楼层
厉害了 牛x!!
我基础比较差,看得眼花撩乱

论坛徽章:
0
发表于 2017-08-22 17:42 |显示全部楼层
本帖最后由 本友会机友会摄友会 于 2017-08-24 11:41 编辑

10人扑鱼数据,我的数据和别人的不一样。奥,错了,10人分鱼,留9份。
重新整理的多人分鱼代码。

  1. function 判断数字是否含有小数部分([decimal]$输入)
  2. {
  3.         if ( ($输入 - [system.math]::Floor($输入)) -ne 0)
  4.         {
  5.                 return $true
  6.         }
  7.         else
  8.         {
  9.                 return $false
  10.         }
  11. }

  12. function 递归求鱼([decimal]$传入数)
  13. {
  14.         if (判断数字是否含有小数部分 $传入数)
  15.         {
  16.                 return
  17.         }
  18.         else
  19.         {
  20.                 $每人醒来看到的鱼数[(0 - $script:当前人)] = $传入数

  21.                 if ($script:当前人 -ge $script:扑鱼达人总数)
  22.                 {
  23.                         Write-Host $每人醒来看到的鱼数
  24.                 }
  25.                 else
  26.                 {
  27.                         $script:当前人++
  28.                         return ( 递归求鱼 ($传入数 * $script:扑鱼达人减一 / $script:扑鱼达人减二 + 1) )
  29.                 }
  30.         }
  31. }

  32. $script:扑鱼达人总数 = 11
  33. $script:扑鱼达人减一 = $script:扑鱼达人总数 - 1
  34. $script:扑鱼达人减二 = $script:扑鱼达人总数 - 2
  35. $每人醒来看到的鱼数 = [System.Array]::CreateInstance([int],$script:扑鱼达人总数)
  36. foreach ($i in 100000000..999999999) #这里给出大数
  37. {
  38.         $script:当前人 = 1 #从最后1人,倒推 5+1 次
  39.         递归求鱼 $i
  40. }
复制代码


论坛徽章:
128
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07巳蛇
日期:2014-05-09 16:43:18巨蟹座
日期:2014-10-23 17:48:38子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59
发表于 2017-08-22 22:58 |显示全部楼层
本帖最后由 jason680 于 2017-08-22 23:57 编辑

本帖目的:
1 递归原理(与编程/脚本无关)
2 用简明代码演示

1 递归原理 (与编程/脚本无关)
  A: 无法立即求得结果/答案
     ex: f(n) = n * f(n-1)
           f(5) = 5 * f(4)
  B: 停止条件 (编写代码时,须先检查)
     ex: f(1) = 1


What You Think Is What You Code(WYTIWYC)
你咋想,就咋编程...

$ cat f.awk

function f(n){
  #停止条件  f(1) = 1
  if(n==1){
    return(1);
  }

  # 无法立即求得结果/答案
  #  f(n) = n * f(n-1)
  return(n * f(n-1));
}
{
  print f($1);
}

$ echo 3 | awk -f f.awk
6

$ echo 5 | awk -f f.awk
120

这里暂不讨论,错误与检查问题
例: f("abc"), f(0.1), f(3.2),...等问题

----------------------------------------------------

如何了解 递归过程...
$ cat f.awk

function f(n, r){
  #停止条件  f(1) = 1
  if(n==1){
    return(1);
  }

  # 无法立即求得结果/答案
  #  f(n) = n * f(n-1)
  printf("%"(++c*2)"sf(%d) call f(%d)\n", " ", n, n-1);     #递归前打印
  r = f(n-1);
  printf("%"(c--*2)"sf(%d)=%d\n", " ", n-1, r);                #递归后打印
  return(n * r);
}
{
  print f($1);
}


$ echo 3 | awk -f f.awk
  f(3) call f(2)
    f(2) call f(1)
    f(1)=1
  f(2)=2
6

$ echo 5 | awk -f f.awk
  f(5) call f(4)
    f(4) call f(3)
      f(3) call f(2)
        f(2) call f(1)
        f(1)=1
      f(2)=2
    f(3)=6
  f(4)=24
120


==============================================
稍为提一下,扑鱼问题,....

分析问题方法有二:

按题意...
1. 给总数,由第1人分配,换第2人, ..., 最后一人分配

反过来...
2.  由最后一人开始分配,反推前一人,....直到第一个人(反推得总数)

p =people
n =number

按题意...
1. 给总数,由第1人分配,换第2人, ..., 最后一人分配

Total fish: n
1.  n1 = n  -1 - (n-1)/p
2.  n2 = n1 -1 - (n1-1)/p
...
N.  nN = n(N-1) - 1 - (n(N-1)-1)/p

ex: People = 5
5.  n5 = n4 -1 - (n4 -1)/5
ex: People = 10
10.  n10 = n9 -1 - (n9 -1)/10

# 无法立即求得结果/答案
平分为p份,余一条(扔回河中),取一份然后回家(人数递减或取鱼者递增)
注:代码取余 n%p ==1

#停止条件
人数递减为0--分配完成(或取鱼者递增与扑鱼人数p相同)

-----------------------------------------------------

反过来...
2.  由最后一人开始分配,反推前一人,....直到第一个人(反推得总数)

最后一人   last1 % p ==1  --> last1 = p+1, 2*p+1, 3*p+1, ....

前一人  last2 = ?   如何反推




n1 = n  -1 - (n-1)/p
后一人 = 前一人  -1 - (前一人-1)/p
last1 = last2  -1 - (last2-1)/p

last1 = (last2  -1) - (last2-1)/p

last1 = (last2  -1) * (1 - 1/p)
last1 = (last2  -1) * ((p-1)/p)
last1 / ((p-1)/p)   = (last2  -1)
(last2  -1)  =  last1 / ((p-1)/p)  
last2  -1   =  last1 * p/(p-1)  
last2        =  last1 * p/(p-1)  +1
注:必须为整数


最后一人   last1 % p ==1  --> last1 = p+1, 2*p+1, 3*p+1, ....
前一人  last2 =  last1 * p/(p-1)  +1
前前一人  last3 =  last2 * p/(p-1)  +1
注:必须为整数


递归原理与分析都有了...
代码就留给你自已写...


论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-08-25 00:45 |显示全部楼层
本帖最后由 rubyish 于 2017-08-24 20:56 编辑

回复 1# 本友会机友会摄友会

数大的话,有人关注性能吗?
1 谁能帮我优化思路,代码?

if powershell no power?
shishi magicperl?

Why perl?

1: good format, beautiful.
biru:
fish.png



2: powerful, zhenshi de power!

shishi!!

# time perl fish 5
  1. 5 1276
  2. 4 1596
  3. 3 1996
  4. 2 2496
  5. 1 3121

  6. real    0m0.013s
  7. user    0m0.007s
  8. sys     0m0.006s
复制代码


# time perl fish 10
  1. 10 3874204881
  2. 9 4304672091
  3. 8 4782968991
  4. 7 5314409991
  5. 6 5904899991
  6. 5 6560999991
  7. 4 7289999991
  8. 3 8099999991
  9. 2 8999999991
  10. 1 9999999991

  11. real    0m0.013s
  12. user    0m0.003s
  13. sys     0m0.010s
复制代码


# time perl fish 12
  1. 12 3423740047321
  2. 11 3734989142533
  3. 10 4074533610037
  4. 9 4444945756405
  5. 8 4849031734261
  6. 7 5289852801013
  7. 6 5770748510197
  8. 5 6295362011125
  9. 4 6867667648501
  10. 3 7492001071093
  11. 2 8173092077557
  12. 1 8916100448245

  13. real    0m0.014s
  14. user    0m0.006s
  15. sys     0m0.008s
复制代码



fish:   (support 3 ~ 13)

  1. # use MAGIC
  2. # use TURBO
  3. # add POWER
  4.                             sub
  5.     _               {##     ins
  6. @   _      =        (##     shi
  7. $   _ [0]  ,    #   )--     hex
  8. $   _ [0]  -    1   ,(#     unp
  9. $   _ [0]  -    1   )**     (#)
  10. $   _ [0]  -    1   )-#     pac
  11.                 1   );;     for
  12.            (    0   ..#     uns
  13. $   _ [1]  )        {       print
  14. $   _ [0]  -    #   )!!     del
  15. $   _      ,    #   );;     @.@
  16. $          "        ,##     sub
  17. $   _ [2]  =    #   )~~     and
  18. $   _ [2]  *    #   )**     (@)
  19. $   _ [0]  +    1   #^^     pus
  20.            ,    #   )**     exi
  21. $          /        ;##     pop
  22. $   _ [2]           /=#     ass
  23. $   _ [1]           }}#     (*)
  24.     _                       pop
复制代码

评分

参与人数 1信誉积分 +6 收起 理由
523066680 + 6 感谢分享

查看全部评分

论坛徽章:
7
戌狗
日期:2013-12-15 20:43:38技术图书徽章
日期:2014-03-05 01:33:12技术图书徽章
日期:2014-03-15 20:31:17未羊
日期:2014-03-25 23:48:20丑牛
日期:2014-04-07 22:37:44巳蛇
日期:2014-04-11 21:58:0915-16赛季CBA联赛之青岛
日期:2016-03-17 20:36:13
发表于 2017-08-25 01:09 |显示全部楼层
my OPT:

TOMORROW~~

论坛徽章:
0
发表于 2017-08-25 13:14 |显示全部楼层
嗯 精雕细琢,版本迭代,永不停歇!

楼上的,扑鱼的捷径算法我还不知道。现在我用穷举傻算很慢,有空我找着算法去。
-------------------------------------------------------------
数大了,解这道题很慢。我又给出【win版,多进程并发,捕鱼代码】。并进行了算法优化。
原理是:
1个经理,n个工人(根据cpu核心数设定。)一个文本,记录任务进度。一个文本用于工人输出。
一 判断工人数,小于cpu核心数,则
二 1个经理,读取任务文本,比如1,调用powershell.exe启动一个工人,把任务给他。
三 写入任务文本进度。比如100001。
四 1---3 循环。经理就是分任务后坐等,随时可以停止经理。
在这个基础上再改改,还可以变成远程并发代码。耗费本地多核,远程多核,解这道题。
-------------------------------------------------------------
进度.ps1

$global:初始值 = 160000000
$global:步进值 = 9999999
-------------------------------------------------------------
  1. #经理.ps1
  2. $并发任务数_总 = 3
  3. foreach ($ii in 1..600)
  4. {
  5.     [string]$想要检测的_运行中的脚本名 = 'g工人_v1.1.ps1'
  6.         $当前用户下_所有命令的命令行 = (get-wmiobject -query "select * from  win32_process").commandline #linux 这里用ps -ef
  7.         $检测出的脚本进程并发数 = 0
  8.         foreach ($temp001 in $当前用户下_所有命令的命令行)
  9.         {
  10.                 if ($temp001 -like "*$想要检测的_运行中的脚本名*")
  11.                 {  
  12.                         $检测出的脚本进程并发数++
  13.                 }
  14.         }

  15.         if ($并发任务数_总 -gt $检测出的脚本进程并发数)
  16.         {
  17.                 write-host '*' -NoNewline
  18.                 & 'e:\练手题2017_001\j进度.ps1'
  19.                 Start-Process -FilePath powershell.exe -ArgumentList " -file e:\g工人_v1.1.ps1  -初始值 $global:初始值  -步进值  $global:步进值"
  20.                 $global:初始值 = $global:初始值 + 10000000
  21.                 $save =
  22. @"
  23. `$global:初始值 = $global:初始值
  24. `$global:步进值 = $global:步进值
  25. "@
  26.                 Set-Content -LiteralPath  'e:\练手题2017_001\j进度.ps1' -Value $save -Encoding Unicode
  27.         }
  28.         Start-Sleep -Seconds 180
  29.         write-host '.' -NoNewline
  30. }
复制代码


-------------------------------------------------------------
  1. #工人.ps1
  2. [CmdletBinding()]
  3. param
  4. (
  5.         [uint64]$初始值,
  6.         [uint64]$步进值
  7. )

  8. function 递归求鱼($传入数)
  9. {
  10.         if ($传入数 -isnot [uint64])
  11.         {
  12.                 return
  13.         }
  14.         else
  15.         {
  16.                 $每人醒来看到的鱼数[(0 - $script:当前人)] = $传入数

  17.                 if ($script:当前人 -ge $script:扑鱼达人总数)
  18.                 {
  19.                         Add-Content -Value $每人醒来看到的鱼数 -Encoding Unicode -LiteralPath 'e:\练手题2017_001\s输出.txt'
  20.                         Add-Content -Value $i -Encoding Unicode -LiteralPath 'e:\练手题2017_001\s输出.txt'
  21.                 }
  22.                 else
  23.                 {
  24.                         $script:当前人++
  25.                         return ( 递归求鱼 ($传入数 * $script:扑鱼达人减一 / $script:扑鱼达人减二 + 1) )
  26.                 }
  27.         }
  28. }

  29. $script:扑鱼达人总数 = 11
  30. $script:扑鱼达人减一 = $script:扑鱼达人总数 - 1
  31. $script:扑鱼达人减二 = $script:扑鱼达人总数 - 2
  32. $每人醒来看到的鱼数 = [System.Array]::CreateInstance([uint64],$script:扑鱼达人总数)
  33. $终止值 = $初始值 + $步进值
  34. for ($i = $初始值;$i -lt $终止值;$i++)
  35. {
  36.         $script:当前人 = 1
  37.         递归求鱼 $i
  38. }
复制代码


关于pk:
用一个特定的山路来pk,然后你知道近路,你绕近路跑到终点了,我输了并不感觉脸红,有能耐暴露出算法呀。


论坛徽章:
10
子鼠
日期:2014-10-11 16:46:482016科比退役纪念章
日期:2017-09-02 15:42:4715-16赛季CBA联赛之佛山
日期:2017-08-28 17:11:5515-16赛季CBA联赛之浙江
日期:2017-08-24 16:55:1715-16赛季CBA联赛之青岛
日期:2017-08-17 19:55:2415-16赛季CBA联赛之天津
日期:2017-06-29 10:34:4315-16赛季CBA联赛之四川
日期:2017-05-16 16:38:55黑曼巴
日期:2016-07-19 15:03:112015亚冠之萨济拖拉机
日期:2015-05-22 11:38:5315-16赛季CBA联赛之山东
日期:2017-11-10 14:32:14
发表于 2017-08-25 16:02 |显示全部楼层
本帖最后由 523066680 于 2017-08-25 16:19 编辑

艾玛,突然之间,我也找到规律了。我就不公布了,且看某人造化。

论坛徽章:
38
辰龙
日期:2013-08-21 15:45:19寅虎
日期:2014-06-09 12:52:17双鱼座
日期:2014-06-10 12:42:44巨蟹座
日期:2014-06-12 23:17:17戌狗
日期:2014-06-17 09:53:29未羊
日期:2014-10-10 13:45:41申猴
日期:2015-03-03 17:21:37亥猪
日期:2015-03-03 17:22:002015亚冠之广州富力
日期:2015-05-12 16:34:522015亚冠之卡尔希纳萨夫
日期:2015-05-24 15:24:35黄金圣斗士
日期:2015-12-02 17:25:08平安夜徽章
日期:2015-12-26 00:06:30
发表于 2017-08-25 17:06 |显示全部楼层
回复 9# 523066680

我去,我也找到规律了,用shell也简单到死呀
您需要登录后才可以回帖 登录 | 注册

本版积分规则

DTCC2018购票6.8折优惠进行时

中国数据库技术大会是国内数据库及大数据领域规模最大、最受欢迎的技术交流盛会。 2018年5月10-12日,第九届中国数据库技术大会将如约而至。本届大会以“数领先机•智赢未来”为主题,设定2大主会场及20个技术专场,邀请来自国内外互联网、金融、教育等行业百余位技术专家,共同探讨Oracle、MySQL、NoSQL、大数据等领域的前瞻性热点话题与技术。
----------------------------------------
优惠时间:2018年2月13日前

报名链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP