猴子问题

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;5 y8 [# i( ?+ C3 A  Y: B
else& \" C2 N" j+ c8 j
link.nextp=i+1;5 Y' l6 p! ^' }5 z, q
  link.number=i;& q- x" r/ a9 k5 a4 L
}
2 h. D/ r3 w) T1 Kprintf("\n");
, F8 {$ H5 C/ t3 Y& ^6 c: |count=0;
: J1 [, H0 x( e) l7 S/ k$ k& Oh=M;. ]: Z& J4 s9 d: d
printf("依次退出的猴子: \n");. P4 T9 D3 o* B8 [& w5 c7 F7 D9 B
while(count<M-1)$ u- {+ }( l5 C+ W
{i=0;4 @# [4 \2 m# ?3 P1 q8 i0 a
while(i!=3)
% F0 G& ~8 i' X2 O: N" H{ h=link[h].nextp;) J- \4 O$ w8 |- W0 d: ~
if(link[h].number)3 D6 m: H9 S% A
   i++;}' ?! Z) D! P$ w3 R9 z8 `
) D7 K' N+ G: C' u
printf("%4d",link[h].number);
( _* w. ?/ `& Xlink[h].number=0;
- _9 l2 }3 P/ l9 fcount++;+ N7 v/ p% a# X
}
2 d! z5 {& e% |4 _7 N% h  \/ A7 V: o3 B6 ^  i. V4 \
printf("\n大王是:");2 B# H1 O7 M1 w: `' b5 J
  for(i=1;i<=M;i++)
$ \) V/ u- b+ P, W) m  if(link.number); I! E' m- T$ i
printf("%3d\n",link.number);
% _! A! {6 W7 Z* j8 K. ~
( B' N' n. ]( k) G% v# v1 u! J4 k3 f* B. n0 i) ~
}
/ X( y/ R6 ]  u8 ^5 a第三种是普通方法for循环
% @) z# y7 J$ g8 t% x#include<stdio.h>
6 ]' i. ]6 R, Z6 p7 j6 P' Pvoid main()
! O) b. j8 f% h8 q1 B{ int i,k,m,n,num[50],q,*p;5 h9 {( M0 o9 M
clrscr();
/ J) F7 a- i  Z8 K9 S7 g printf("input number of person: n=");. v! M7 ^( o0 @
scanf("%d",&n);0 s  q* u! G, W7 \( j( A
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只( M4 R! N5 H; o4 g6 y  t/ y3 }7 I
scanf("%d",&q);5 y: [# [$ J2 t$ W$ c
p=num;
* @: @. M0 V$ n! F$ b) T  for(i=0;i<n;i++), J& d+ z3 A: O, \+ p
*(p+i)=i+1;
6 c0 u5 a4 X0 F. y1 j/ v. o i=0;
: A, E2 v' ~' N$ i$ F4 Q k=0;
0 f7 h4 w" p& ~1 W/ e! O& Y6 H m=0;% l, m; Q' X- R, I; m% u
  while(m<n-1)! C  J/ b6 a& V2 F& ]
{if(*(p+i)!=0) k++;
$ b, C7 s) `4 Z0 P4 c+ K5 |" x5 M    if(k==q)' f' U: L& A9 }) }" f! c3 a  b* {
   { *(p+i)=0;
' v3 H! ~8 K; ~6 q9 F9 m. K( a       k=0;
4 E; D0 w; i4 T# b7 E: t       m++;2 X+ L: T( Y) ]' x# e5 f* q, v
   }- a" [2 v$ z- r- ^, P& c7 @
i++;
* h$ s. p1 \  U if(i==n)i=0;
0 z# W5 K" F* d7 q- b% X9 C }
  J& }  |& D8 q5 M  while(*p==0)p++;. s5 Q; ?  X2 d5 x  n+ c
printf("The last one is NO:%d\n",*p);
  L1 F" _% G% b    getch();
  a2 W* K0 b3 q+ }) w( b5 I; [- q7 Y  L% Y2 K1 q9 Q
}

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

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

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

猴子问题

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

版权声明