猴子问题

HACKER · 发表于 2011-10-2 03:45:38

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

×

大家好!
这几天我在忙着编一个问题,我用了一种方法编出来!
但是当我编完时我去看书! 发现许多的方法我看了看,拿出来与大家共享!还有附件哦!
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激

                        题目
山上有m只猴子要选大王,选举办法如下：所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
第一种方法：利用循环链表
#include<stdio.h>
#include<malloc.h>
#define M 8          //共有8只猴子
#define N 3          //数到3只时退出第三只
typedef struct monkey
{int number;
int flag;
struct monkey* next;
}MONKEY;
main()
{ MONKEY *head=NULL,*p,*s;
  int i,sum=0,count=0;
  clrscr();             //清屏
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  p->number=1;p->flag=1;
  p->next=head;
  head=p;
  for(i=2;i<=M;i++)
{ s=(MONKEY *)malloc(sizeof(MONKEY));
   s->number=i;s->flag=1;
   s->next=head;
   p->next=s;p=p->next;
}
p=head;
for(;;)
{if(p->flag==1)
   count++;
   if(count==N)
      {p->flag=0;
      count=0;
      sum++;}
   if(sum==M-1)
      break;
   p=p->next;
}
p=
head;
for(i=1;i<=M;i++)
{ if(p->flag==1)
      printf("\t%d",p->number);
   p=p->next;
}

}
第二种方法：数组
#include<stdio.h>
#define M 8
struct monkey
{int number;
int nextp;
}link[M+1];

void main()
{int i,count,h;
for(i=1;i<=M;i++)
{  if(i==M)
link.nextp=1;
, @/ c$ I- k* j  X8 u8 ` else
: g3 [3 N5 n  I7 V3 g* h link.nextp=i+1;
' h. R" g6 m2 R$ @* f; {' |  link.number=i;
. T. ^3 Y0 ~5 Y% k+ R/ m}1 F& m. Z" n$ b: [$ @; d
printf("\n");) t8 `+ h. {; ]; e2 _* m
count=0;
& e) K. p1 N9 a5 Z0 Y# sh=M;0 [" ?1 t* E6 G8 i
printf("依次退出的猴子: \n");
; g0 X6 l# x! W% z/ N  Ewhile(count<M-1)
# w7 x0 E# y% W{i=0;1 H2 {5 W" t0 A1 [7 ^$ o1 R3 ^
while(i!=3)
+ F: y) U7 |: ~) G{ h=link[h].nextp;
3 G0 h7 `$ K/ v if(link[h].number)  d0 V' }7 C* D' W! \7 @: f
   i++;}
  ]. i/ w, y+ A6 c) P# c, Q, `# z/ _% p: J# L
printf("%4d",link[h].number);
6 t- K. `9 H) j6 F2 {  J6 S2 dlink[h].number=0;
$ ]+ v! I' j* u, i/ Lcount++;
/ k, V4 C7 P7 X3 T% \+ G) A}) r3 u" R  K9 }+ L8 q$ W; F; r/ J
0 f5 `, G, Z1 [
printf("\n大王是:");
9 m" ~  n5 m$ J3 J. e/ F+ M# o  for(i=1;i<=M;i++)7 M3 x% }! |( m$ d' i
  if(link.number)
$ k5 I* A7 m  D3 ~' Y+ ` printf("%3d\n",link.number);2 v* G8 U! d  A7 c

; D; s) ]' U" e' E8 t- f& e* q& D" k9 T
} ' G; R& G% g% P( Y2 l$ g
第三种是普通方法for循环7 p$ z; g0 N3 D* ~* h7 o* H# v
#include<stdio.h>
" q  n$ l. ~3 R7 \8 l6 y: pvoid main()3 `3 |1 X! Q; M1 ^$ v" u+ w
{ int i,k,m,n,num[50],q,*p;" k8 v' I2 ?9 \- P
clrscr();
  B  l0 n2 Q, @+ Q% e! y, i printf("input number of person: n=");
; v9 g9 n" C# r' L7 V4 J% @9 D scanf("%d",&n);
7 T- Z# ]9 x. S; t6 n5 Oprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ }* x3 O1 n6 j" V2 b/ [
scanf("%d",&q);/ B) f& w) y1 }9 u" R
p=num;3 ], K% _" I' K- J
  for(i=0;i<n;i++)8 H5 F( K) W/ t
*(p+i)=i+1;$ d4 c( ~2 w8 h- A8 x. w
i=0;: }  O! Q" b3 Z# N" ?2 E
k=0;
% x+ f, o% c$ Y, Q m=0;
) {$ f" j; O3 k0 \  while(m<n-1)
" }2 C# g7 K+ q' _7 I  J3 A, q {if(*(p+i)!=0) k++;
0 U1 V! e* T# B; P: W8 K6 |    if(k==q)
$ i* c& c3 @3 D1 b- D& L* I" ?* g    { *(p+i)=0;, F  M. v' v# I. r9 J. p
      k=0;
4 q5 D$ G2 q, q. s: s: N7 \3 ~4 l4 t6 f       m++;1 P  w- T4 k+ h7 T. l! c
   }8 P* q% ?" u' D
i++;+ h& X  o6 k& c( {, c8 S
if(i==n)i=0;
& @: G3 s9 [9 f0 k }
- Y" @3 g; V& v+ b2 d9 l* Z  while(*p==0)p++;, ~) d. H9 [( J& h9 T4 d' ^
printf("The last one is NO:%d\n",*p);
" ?8 J3 ~: A0 m2 n; ^3 n( q    getch();% p& k) F% m% `9 X5 T
( G# n! o1 i5 K4 E% E# W
}

寒砧-LAMP · 发表于 2011-10-24 17:28:46

{:1_1:}这个题以前读大学的时候做过！我是用C#语言写的！待会儿拿出来共享

寒砧-LAMP · 发表于 2011-10-24 17:32:28

using System;
namespace 又费马达又费电
{
class Program
{
      static void Main(string[] args)
      {
         int m, n;
         Console.WriteLine("请输入数组长度");
         m = int.Parse(Console.ReadLine());//m为数组的大小
         Console.WriteLine("请输入要截取数字的大小");
         n = int.Parse(Console.ReadLine());
         int [] numw=new int

;
         for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
         {
            numw[j - 1] = j;
         }
         int i = 0, k = 0, d = 0;//声明一组变量给while使用哈！！
         while (d != m - 1)
         {
            if (i == m && d != m - 1)
            {
               i = 0;//i控制每次遍历数组的变量，用它一次次遍历数组的啊！！
                  continue;
            }
            else
            {
                  if (numw[i] != 0)
                  {
                     i++;
                     k++;
                     if (k == n)
                     {
                        numw[i - 1] = 0;//把在n位置数组元素的值改变了
                        k = 0;
            d++;//每改变一次数组中元素的值，d就自动加1，但要比数组的长度小1
                  Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
                     }
                     else//输出暂时还没有改变数组元素的值
                  Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
                  }
                  else
                     i++;//数组元素为0，直接跳过，不计数。。。
            }

         }//结束while循环
         for (i = 0; i < m; i++)//输出剩下那个数字，得到最终结果了哦

            if (numw[i] != 0)
                  Console.WriteLine(numw[i]);

         Console.ReadLine();
      }
}
}

祇逑_铵乐 · 发表于 2011-12-28 07:02:23

循环队列。循环链表。。。

祇逑_铵乐 · 发表于 2011-12-28 07:02:46

这个题目就是经典的约瑟夫环

账号		自动登录	找回密码
密码			立即注册

猴子问题

马上注册，结交更多好友，享用更多功能^_^

版权声明