猴子问题

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;
+ }+ p4 x& g7 u! {1 A/ F% u& w else3 g& t- E. U" I5 w" Y
link.nextp=i+1;" Q5 H0 D' {  F" ^$ ?& U
  link.number=i;# n8 [- ^: ?: T- t
}" c% d/ x8 |# X+ S8 K
printf("\n");
9 e$ w: ?7 e7 A  J# K0 Jcount=0;: ?0 R, g4 Y% E* v
h=M;
6 C% N8 b: R4 D( f* p& Oprintf("依次退出的猴子: \n");0 D) v  z+ X1 D3 k( p( {
while(count<M-1)
7 ]/ y7 N  w  B: b% I( o3 B{i=0;
  E$ \+ l8 N. Z1 Wwhile(i!=3)
$ S) r- O% c. G% \, {. e6 q{ h=link[h].nextp;
' Y6 |- P. t2 v1 F3 h: Y3 f if(link[h].number)! v, l5 G8 V+ O% \! ?
   i++;}
7 p2 u1 f4 z7 ~; S& k1 b4 d) `9 N
printf("%4d",link[h].number);% ~8 E5 I5 M6 k. O, ]
link[h].number=0;% h' N4 L1 O4 Z) P2 ^( `5 ~
count++;% G& Q" T4 i8 P' N+ @4 d/ H
}: B" Y0 i5 V9 N$ l' H( T7 J
+ A/ b* l$ Q7 X* A& F! n0 b" D4 ]
printf("\n大王是:");" l' L0 w3 y% ~; O/ `
  for(i=1;i<=M;i++)
' M9 }9 @, L3 V. }- Y# ~  _  if(link.number), e) c8 e: ?/ l3 x2 R4 i2 t6 }
printf("%3d\n",link.number);
2 P2 C% H4 F) f8 {8 l
1 _" y2 l+ S$ M5 N% {8 K4 \6 q
! s7 t- |+ T# P4 N} / b) G0 e* j; _3 @* @+ x2 `
第三种是普通方法for循环
/ Z; I  H6 I& H  f% ?& D) i#include<stdio.h>+ O% G* F( U5 e+ H# l/ o5 E5 E
void main()  v0 f' L: S4 ?5 t6 s" |# Q7 @7 c
{ int i,k,m,n,num[50],q,*p;
7 g5 M2 L+ }; L clrscr();7 b3 S- r9 @4 u6 P
printf("input number of person: n=");
$ R% q7 ~) x9 ]/ ?. T$ Q8 g. c scanf("%d",&n);
- n( T7 O' [1 A: ?8 `) x5 xprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
! h! P. \* h* S* ~+ C/ z scanf("%d",&q);
, M9 K( u) k: B4 K3 a8 I6 Z p=num;" a7 _6 h% Z: u
  for(i=0;i<n;i++)
* F* f$ q- k& m/ ]# q4 y- a. u *(p+i)=i+1;6 V1 }: h1 e/ q# }; w# Z: {
i=0;, O2 R" c! s2 n7 e
k=0;' K" u+ g. ^/ E+ v8 Y
m=0;4 _/ h. b# D: `  l6 e& b( I8 G1 j
  while(m<n-1)% R4 t6 U: n( z
{if(*(p+i)!=0) k++;
% ?# j8 ]1 r- m2 b* O' ^) G    if(k==q)
' {& E6 C' D; Q) u, F: [    { *(p+i)=0;$ W4 O2 O6 b4 Q5 u/ h( P/ ?# |
      k=0;
  i9 E- ^- m/ w1 _. K       m++;5 E- }8 s0 S/ l. ~6 o& z) U
   }. v, L& d: G8 _/ Z
i++;
7 n# V3 @/ [& D( J if(i==n)i=0;: S: D% E5 u5 ^9 a2 E
}
/ E9 Z2 E) A$ ]$ x. }  while(*p==0)p++;
3 I9 E) A4 _; G3 k5 Z0 K printf("The last one is NO:%d\n",*p);
' f; g% B5 Q. ~3 y    getch();6 b5 m) p6 h1 u% t

" {$ F3 {8 O& P3 A5 }& z2 i) t, e}

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

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

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

猴子问题

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

版权声明