猴子问题

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;/ Z8 u8 }( S  m: J& m+ k( C0 [
else: r9 X* l0 u5 \' P" o$ J
link.nextp=i+1;' s, U9 j6 U- \! G0 J5 x
  link.number=i;: y7 ~- \. t, }% I$ v- f! g; N- {' d
}
. ]: C7 ]( B5 e8 _; ]# fprintf("\n");
& M9 A; m( W/ ~5 t; H) c" p0 jcount=0;, ]& |4 k1 \% u+ _# Y$ b
h=M;* r* e; a% E' o' h
printf("依次退出的猴子: \n");
while(count<M-1)
* R* l; O* t3 ~5 }{i=0;0 A- {' L1 R9 Q
while(i!=3)
7 m8 ~* O0 a! }( \- _{ h=link[h].nextp;
* ?. s$ E1 a* o- d& ?  P& f if(link[h].number)3 N1 C  A; M4 y# Q
   i++;}
8 e' L% o) f$ r' m- ~1 P( u0 \1 p* ]& k
printf("%4d",link[h].number);2 ?2 _. q6 j% d& L0 z4 i
link[h].number=0;
# ~' W. ^% w7 b; Y' Ucount++;
  q+ ~1 }( D. A  e* \" u. v+ r}
8 V8 r# {2 R" d: M: l# c0 ^: v3 ]5 E" d4 M9 o( h; `; p
printf("\n大王是:");
5 C) j8 f) z3 r$ S2 N) r% ?. M  for(i=1;i<=M;i++)
6 m8 w3 W6 x* W6 i- {: }  if(link.number)
. x; s8 h! A8 m4 D* M5 q# b printf("%3d\n",link.number);4 Z( ~6 }1 {, _2 p( O, ^: ?

" m/ ?0 O; d9 P) k) W7 A0 [9 F
" T/ s  k$ M8 p5 o7 x3 H}
9 I2 u) z; _7 R: h: H9 z第三种是普通方法for循环6 {1 Y$ R& C% g0 [2 R
#include<stdio.h>) f" S/ @/ t+ K$ y6 t
void main()3 |! K% \/ {! f  k5 v: G
{ int i,k,m,n,num[50],q,*p;& b0 h: G' z  [& [
clrscr();$ O& t: J) R; j" h0 F
printf("input number of person: n=");" E9 @+ ~3 l9 n! _# A
scanf("%d",&n);
7 C. b1 t7 |' ?4 Z7 dprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只! B4 o) ^4 @# ^
scanf("%d",&q);
% I9 B4 D. |! s- C* w7 z p=num;* B7 O& ]) s2 A3 M: X4 C
  for(i=0;i<n;i++)
/ S) y0 l+ s" _7 p2 W$ k' d" b' k *(p+i)=i+1;
. z- j2 U7 F$ n/ W0 m" f) x i=0;. X# O- U4 L. {: Q, g6 ?$ H
k=0;
+ ]3 c! a+ `7 V) E; i m=0;1 c# K) {: y3 \* |
  while(m<n-1)% L/ K2 ^7 V3 o- a3 X: V! D
{if(*(p+i)!=0) k++;1 ]  }/ s9 K& j" n( a- }
   if(k==q); s' H. N- P6 R
   { *(p+i)=0;
. v; ~. B3 c) ^6 p       k=0;  L. s: P) _/ F, h5 _
      m++;
# A, N3 G( M* v+ R! R, J    }
# F- k5 F) M( l* O- l i++;1 U, _* a8 ^7 n4 m
if(i==n)i=0;
4 J7 B# T/ ^+ j( q! O8 j. y: e* s' o }1 U- ~. v/ j( w4 I! i! x
  while(*p==0)p++;
# V$ V, B7 Z+ m3 _ printf("The last one is NO:%d\n",*p);6 \, X6 f; Q0 ~. j9 f
   getch();
4 h5 e. S% J3 L1 @/ \% J6 L1 C2 h/ O: |! r
}

寒砧-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

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

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

猴子问题

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

版权声明