猴子问题

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;
1 V  U, y# i/ o/ C0 T+ j9 M, V8 @ else
! X1 h" [( t7 y! | link.nextp=i+1;
6 n( M3 b" s! m8 R  p  link.number=i;+ k3 X6 k: y" E1 \4 r
}& C* y5 |( B2 I$ o% F
printf("\n");
- `  t1 N0 ]' o( E- tcount=0;
; P7 u* V9 m' m9 b- N0 t: x7 R1 qh=M;6 V% H: ]8 m; V% b
printf("依次退出的猴子: \n");
/ r% N. Z+ T2 ]- X" z: Uwhile(count<M-1)
4 _1 q# N: _# X" j& c/ }{i=0;1 r* T- i# ~3 }, @" ]
while(i!=3)
4 b$ I% z# \9 R( n7 B' o{ h=link[h].nextp;
, S8 x& S; E; a6 H; K' n if(link[h].number)* H9 _& f7 b* e( i! l9 R) [% {8 f
   i++;}
, g; C0 s8 q* @3 A& l- Z1 _  }
9 }- v' U9 Z. u" yprintf("%4d",link[h].number);) ^6 A/ T) Q$ @8 n
link[h].number=0;
8 |5 y6 c" Z0 G1 _' N+ fcount++;) o9 f- e& [& X+ t
}- p; Z4 J. [1 L4 h9 `
, E0 X. S( S( B/ n' D
printf("\n大王是:");
% n0 z1 [8 g1 B8 U! V: Q% H9 c7 D  for(i=1;i<=M;i++)
2 B& _& A+ Z8 ?. ]/ q- ^  if(link.number)
# S7 c. i. K) J% E: y printf("%3d\n",link.number);
' o7 b/ z+ Y' m+ E8 n. n# L# {9 {" X. X

7 G/ p9 c: T0 c8 R" F6 h: Z# x} : _6 h3 I5 d& z- `" A
第三种是普通方法for循环
2 `  c: g! b$ B! T#include<stdio.h>
! p- B7 J, H: j9 m4 P% A/ K3 nvoid main()
$ p2 F1 `) Y0 M5 `& T{ int i,k,m,n,num[50],q,*p;* `' _; T) ^2 V# t; @  e. E
clrscr();
, c$ f8 @; k4 h9 F printf("input number of person: n=");
2 k2 u, i. z5 w scanf("%d",&n);
4 i5 |& ?4 m9 l( x5 B" qprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只, p6 Y4 O6 j1 u1 c9 _& c( ~8 c
scanf("%d",&q);
; |' a* W9 B  m, h4 m) P5 j p=num;
/ D4 a$ L7 K) m  C6 [5 K3 {. u  for(i=0;i<n;i++)
7 w8 h( Y6 {. ]/ e6 j3 q6 d *(p+i)=i+1;2 H5 }& C) Z5 f4 f* I8 A/ a% [4 P
i=0;
' _6 r- y" @4 p9 D k=0;  r! ^" |: ?4 l7 Q
m=0;
0 [8 J2 V! {+ [. `  V; T  while(m<n-1)/ F8 T) u, S; R& q
{if(*(p+i)!=0) k++;+ [! Z1 ]2 t0 ?: c! S1 M/ s0 \
   if(k==q)/ E) ?- v6 {/ a  E! x, {
   { *(p+i)=0;
$ i, f. |3 a+ Y" u- J3 x6 i, S, X: H       k=0;: d& `* h9 m$ i( I' s+ m; S; r
      m++;
$ R2 M2 X8 c% v/ v# q, V    }
/ x  b( V- F  J0 h i++;
2 l: d% V+ r& O" C7 G! f- I if(i==n)i=0;
0 @1 P! K3 Z) s* S, Q! G }
0 o# H: n' W% F5 @* e) c  while(*p==0)p++;, U* g3 J+ i7 W& M8 x- ?# z
printf("The last one is NO:%d\n",*p);
$ \- L4 \' y- z' B1 ?3 x* P    getch();
: G+ ]6 t6 L0 Z+ e2 g: Q; r' w$ M" H- f1 z
}

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

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

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

猴子问题

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

版权声明