[powershell]猴子选大王问题

dorodaloo

遇见这样一道题：

一群猴子排成一圈，按1，2，...，n依次编号。然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，再数到第m只，在把它踢出去...，
如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。
要求编程输入m、n,如 choose(100, 3)

1. choose(n, m)

复制代码

输出最后那个猴大王的编号。

谢谢!

dorodaloo

大家开动脑筋吧，
shell 怎么写出代码？
poershell 怎么写出代码？

sunzhiguolu

1. #!/usr/bin/perl
   
2. use strict;
   
3. use warnings;
   
4. 
   
5. my ($n, $m, $try) = (10, 5, 0);
   
6. my %hNums = map {$_, $_} 1 .. $n;
   
7. my @aBox = ();
   
8. 
   
9. while(1 < grep {$hNums{$_}} keys %hNums){
   
10.         {
    
11.                 push(@aBox, $try) if($hNums{$try});
    
12.                 if($try > keys %hNums){
    
13.                         ($try) = sort {$a <=> $b} grep {$hNums{$_} and $try < $_} keys %hNums;
    
14.                 }
    
15.                 if(@aBox != $m){
    
16.                         $try++;
    
17.                         redo;
    
18.                 }
    
19.         }
    
20.         print("$aBox[-1] is out!\n");
    
21.         $hNums{$aBox[-1]} = 0;
    
22.         $try = $aBox[-1] + 1;
    
23.         @aBox = ();
    
24. }

复制代码

perl abc.pl
---------------------------------
5 is out!
10 is out!
6 is out!
2 is out!
9 is out!
8 is out!
1 is out!
4 is out!
7 is out!

jason680

回复 3# dorodaloo

$ awk -vn=10 -vm=5 'BEGIN{printf "out=";for(c=1;c<=n;++c)a[c]=c;choose(n,m)}function choose(n,m,p){if(++C>100)exit;if(n==1){print "\nKing="a[1];exit};p=(p+m-1)%n+1;printf " "a[p];for(c=p;c<n;++c)a[c]=a[c+1];choose(n-1,m,p-1)}'
out= 5 10 6 2 9 8 1 4 7
King=3

$ awk -vn=3 -vm=100 'BEGIN{printf "out=";for(c=1;c<=n;++c)a[c]=c;choose(n,m)}function choose(n,m,p){if(++C>100)exit;if(n==1){print "\nKing="a[1];exit};p=(p+m-1)%n+1;printf " "a[p];for(c=p;c<n;++c)a[c]=a[c+1];choose(n-1,m,p-1)}'
out= 1 3
King=2

$ awk -vn=100 -vm=3 'BEGIN{printf "out=";for(c=1;c<=n;++c)a[c]=c;choose(n,m)}function choose(n,m,p){if(++C>100)exit;if(n==1){print "\nKing="a[1];exit};p=(p+m-1)%n+1;printf " "a[p];for(c=p;c<n;++c)a[c]=a[c+1];choose(n-1,m,p-1)}'
out= 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 2 7 11 16 20 25 29 34 38 43 47 52 56 61 65 70 74 79 83 88 92 97 1 8 14 22 28 35 41 49 55 62 68 76 82 89 95 4 13 23 32 44 53 64 73 85 94 5 19 37 50 67 80 98 17 40 59 86 10 46 77 26 71 31 100 58
King=91

moperyblue

1. #!/usr/bin/env python
   
2. # encoding:utf-8
   
3. 
   
4. def choose(n, m):
   
5.     l = ["monkey-" + str(i + 1) for i in xrange(n)]
   
6.     idx = 0
   
7.     cnt = 0
   
8. 
   
9.     while (len(l) > 1):
   
10.         if idx == len(l):
    
11.             idx = 0
    
12.         cnt += 1
    
13.         if cnt == m:
    
14.             print l[idx] + " => out..."
    
15.             l.remove(l[idx])
    
16.             cnt = 0
    
17.             continue
    
18.         idx += 1
    
19.     print "==================\n" + l[0] + " => king"
    
20. 
    
21. choose(10, 3)

复制代码

dorodaloo

这个是真的非常厉害了
谢谢
刚试了一下，perl不符合要求