猴子问题

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;3 C7 t1 L5 o" V$ o) H
else
  z. g& w) G( \: [) _ link.nextp=i+1;3 J+ \: R* {4 ?. T5 U
  link.number=i;+ @' o# y1 B- g3 K" U
}
3 x1 F1 d7 [4 A1 hprintf("\n");
' p* T3 v. Q: o7 u) e8 w/ R5 S3 ucount=0;
( E4 g+ h% C+ @h=M;2 p7 a/ I. Y( Q5 W% C& w
printf("依次退出的猴子: \n");
4 J" A, S. j  a3 Awhile(count<M-1)6 e" N3 X/ L8 m
{i=0;
" H* i  H' S3 t3 j. k: c. F; v  Jwhile(i!=3)# s; D- M/ d  y2 J( L9 e5 \
{ h=link[h].nextp;
$ L: l) K2 ^# ]% V" ?" B" W if(link[h].number)
  u2 T3 S4 O* c2 i    i++;}
" O& i* N' r, \+ x: f$ F$ ]2 ~5 W* M! }6 s
printf("%4d",link[h].number);0 Z, N+ l* G8 f, J. c
link[h].number=0;
2 q8 w6 y, A3 l* l+ Icount++;
- f, V- s0 E& R% u* G. z+ k}
% B/ ~' E# ]8 Y8 `: J) z* |$ u. `# F  n6 X" q1 v' y
printf("\n大王是:");
% q) H3 v$ J2 W; I5 L  for(i=1;i<=M;i++)
% \' q; u6 U! O  if(link.number)
" n5 Q2 L( o5 C7 J4 m" h printf("%3d\n",link.number);: l3 w1 U8 [: \7 `1 o7 U5 Z$ |

8 J+ u/ _& X/ Q! R; c* P
+ V% A- Z# [, S9 M} 5 F" V7 L% N, J# z1 ]3 x  }9 h
第三种是普通方法for循环
9 |; B9 j3 S* a#include<stdio.h>
$ l' b( Q9 g0 A, f0 ?- ^void main()
9 X4 l  l9 x& S" H2 x{ int i,k,m,n,num[50],q,*p;& B9 d. J# i3 c4 w
clrscr();9 Y% a( Z) x/ H0 B/ ]; u& t
printf("input number of person: n=");" C8 Q4 n+ h( a/ C3 k
scanf("%d",&n);- S! G8 }$ i/ [% v3 P- k
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只6 [- ]7 T: e1 s) _2 D  Q) o
scanf("%d",&q);+ V  x4 M* H/ F% Z; g2 {  {
p=num;
! j1 \1 p! E/ }  for(i=0;i<n;i++)
, c6 ?& k# |1 H) E( k *(p+i)=i+1;
, s( L7 L# @; `% F( v( y i=0;  C5 [: U& \0 `/ z
k=0;0 T: R- p- C( ~' i
m=0;! G; ?! h# P! l/ r4 `# i& B
  while(m<n-1)* e3 o* S$ m1 V/ h  D3 w' M
{if(*(p+i)!=0) k++;0 l; G$ f- k8 l
   if(k==q)" {! S6 {6 {+ ?" h, r9 J
   { *(p+i)=0;
3 V) v( Q: X9 f" g- C/ h       k=0;' t' O( Z8 y- H2 N' ?$ p
      m++;
5 C" _9 l" a! W; e    }8 h7 }% q5 `4 Y. |+ S
i++;5 p$ h3 B. T# X
if(i==n)i=0;* q* U0 l) N" ?, [# A% b
}: g3 Q; Q7 V  x& _
  while(*p==0)p++;
" _- h2 y: r% P" ] printf("The last one is NO:%d\n",*p);6 J' P, N: T& H" m7 o
   getch();4 l: \% f) r( e8 A& h4 B$ ^

4 Y" D/ ?7 Y) Q3 |* {1 D% o7 X}

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

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

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

猴子问题

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

版权声明