猴子问题

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;
) O# f& n+ E1 M: i: e else
5 e- e$ y9 Y3 H6 F link.nextp=i+1;" O% R- X, |. }9 Q$ k3 H
  link.number=i;" C; |( @1 n! _  c' D2 U
}
1 A8 q6 H) C$ A" e8 t/ Rprintf("\n");
8 R7 H% B8 b3 e5 Mcount=0;9 F0 ?7 x$ L, g, b% e! E
h=M;
, {9 o+ x0 g" S8 e. _, Vprintf("依次退出的猴子: \n");
& i9 V1 P: u5 N4 B3 Twhile(count<M-1)
; k! ], Y  s# Y" {( c$ U2 B{i=0;
/ y0 K0 o5 X; e( s  ]0 ]+ \7 Ewhile(i!=3)1 f, _1 j& _9 }$ l6 B1 Q- j. P% s( P; I
{ h=link[h].nextp;# {6 ?4 C) S1 F: Y2 v* I
if(link[h].number)
% w- D& \- S6 p$ W) b* _    i++;}0 ~1 T0 N0 \! @) ^0 W

5 E+ c' b1 x" S: N1 a4 uprintf("%4d",link[h].number);
/ b- i* f8 C, H2 n0 }+ @" m# Hlink[h].number=0;
) c4 K" v2 q" s- t" c" y& b% l: d, lcount++;& B. z1 |# w2 k
}
$ n1 q4 S2 S4 L- g
; L; [6 V; j% G& Tprintf("\n大王是:");
) u4 ?8 i) I9 y. j  for(i=1;i<=M;i++)
( B) q' b( s4 R  if(link.number)8 Z9 R! b7 P9 h- L
printf("%3d\n",link.number);
  U9 s: s! E: D
+ Q$ L3 P" w8 H- x1 s: q( a$ N) N5 M! e: B+ D& ^3 H
} ' F! F% W0 n0 v/ [+ s
第三种是普通方法for循环, r1 L. F1 T6 s6 Q* a" [
#include<stdio.h>( k& Q4 q6 P0 i
void main()
6 y4 w  `0 V2 c( n# Q# u{ int i,k,m,n,num[50],q,*p;0 A% S' S9 J" a: @. I. I5 t
clrscr();/ k' P$ m  P! z& h( ]
printf("input number of person: n=");6 z1 i% G# b& M! N- ^
scanf("%d",&n);
0 v/ V/ v0 }- j8 D* iprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- x9 \& f  u( N4 l+ @( M. e" g scanf("%d",&q);" R. v" N  c2 Z& Q' `( h4 ]
p=num;9 j# i2 k0 s% g: [
  for(i=0;i<n;i++)
( [* O3 j8 U; f$ i *(p+i)=i+1;# P7 k" {. J7 G
i=0;
6 r& x7 W5 m! U3 x; G3 ^) q$ r) y k=0;
8 T7 C* A. E# i( L  x m=0;1 R1 ~0 U( e! t* e1 f0 O- B( L
  while(m<n-1)
. \+ D) x2 k7 a {if(*(p+i)!=0) k++;
2 e1 X. v$ h* a1 A# k9 j6 a9 r    if(k==q)3 D/ d4 g0 x; r/ e8 r
   { *(p+i)=0;
1 ^& P" u0 [, s( Y       k=0;$ u. E* ]0 W+ _' `3 y1 X6 o
      m++;2 B' ^0 Q$ L) T/ N+ q
   }
! w+ D5 h- d- _& H i++;( B, F. [2 D& @2 U
if(i==n)i=0;
9 |; ]# _! B8 ^: t# s9 l }
0 m4 V% |1 t/ \8 y! Z  while(*p==0)p++;
+ p. z+ ~( x! r printf("The last one is NO:%d\n",*p);
" _( o& f- m9 _9 M    getch();
: _2 S5 g) K$ J- V) U% A! z
! a& B3 k9 [/ c' [. }( D% c}

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

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

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

猴子问题

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

版权声明