猴子问题

HACKER · 发表于 2011-10-2 03:45:38

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

您需要登录才可以下载或查看，没有账号？立即注册

x

大家好!
这几天我在忙着编一个问题,我用了一种方法编出来!
但是当我编完时我去看书! 发现许多的方法我看了看,拿出来与大家共享!还有附件哦!
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激

                        题目
山上有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;
4 L1 C: i# O0 u) l$ y else
. D! D& D0 n# H. w  x8 P4 o' C7 L link.nextp=i+1;# l( z5 `+ t& _1 H
  link.number=i;+ V( U  a& V7 Q# K
}
) h" f4 [; ]& n1 Bprintf("\n");
+ h$ n6 p2 R, V+ lcount=0;
) ]+ V( J3 v. R2 }* a* Yh=M;% c8 u' `0 U/ W& A9 l; V
printf("依次退出的猴子: \n");
% F! h3 n" P$ [# Q# z2 dwhile(count<M-1)
' _! [; Q# U5 H# G{i=0;
" ~. h; I& G" I* Q- ^8 M! [while(i!=3)* P: ^# t6 |6 B: H1 b, u
{ h=link[h].nextp;* L* G5 E, N' x6 S2 V
if(link[h].number)
) N- {9 R1 H6 v! y$ `    i++;}% b, d6 C0 I5 ^- E

) d0 R9 Q: b. G9 t4 I' _printf("%4d",link[h].number);
3 {/ i; f6 b/ a9 c$ Flink[h].number=0;
: X8 S" E# F. e" G  t2 L: kcount++;
4 `8 D, g% R. A}
7 ]' P. C. j3 N6 t
3 [, p7 n1 J: b( h2 y' ?2 D+ {printf("\n大王是:");. G( b% a8 t8 P& P
  for(i=1;i<=M;i++)5 w0 W2 d- ^7 c, M
  if(link.number)
, R& \: _9 [  w9 ^3 k/ k printf("%3d\n",link.number);, P7 E8 c: K/ P/ K+ j% F9 t) E

6 K# n2 T5 d' ?  C
/ D$ v9 B( w) t1 e& }0 J7 W}
& k4 p4 U, o( ~& h, P- A" ^第三种是普通方法for循环' G* w! b, }* L5 U- M1 J
#include<stdio.h>
8 I( ]1 @" b1 {! P  {5 Nvoid main()
9 E' J: ~' @& W' B{ int i,k,m,n,num[50],q,*p;0 R+ P4 D' J6 _( l% d
clrscr();6 p# a5 P4 f, v; |% \9 I& m
printf("input number of person: n=");" q! g2 g% L2 L3 X- |  s
scanf("%d",&n);$ t( W7 D4 r9 w
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只0 |( g3 }# g6 d% G) B  L% @& o
scanf("%d",&q);  ?! b0 M6 x( B7 ]  s
p=num;. z+ a# u1 \$ d+ ~/ p" p; i
  for(i=0;i<n;i++)
, V, B4 H7 [$ W* y *(p+i)=i+1;
  _. a! u8 x5 d/ j! H i=0;
( ?" T! R$ z2 C3 I. Y/ n, t! k k=0;
- X$ C' h4 P, C, v6 Q1 k: H3 R m=0;% F6 d5 q5 @9 D- X0 f
  while(m<n-1)! M4 G+ {3 Z! F/ `% Y8 _8 l, z
{if(*(p+i)!=0) k++;5 v+ ~- \5 D- _" p: c% ]! R" a
   if(k==q)7 ?* c" b8 G$ u  l! }' J
   { *(p+i)=0;  N; Z, c8 O9 e+ t/ l2 }! P
      k=0;  Q( @8 n% D( g* D& B3 I: V
      m++;
7 I9 W. _2 b, P4 J: f    }
3 d& \( f) u) y! M i++;7 ]) p5 \7 `8 i) X+ R6 u& j  `
if(i==n)i=0;
% P+ W3 R" q0 b9 E) f }+ ~! W& C1 Z( ~; O
  while(*p==0)p++;
* k! \* Q. }! J6 d/ ?$ a4 f: j2 M printf("The last one is NO:%d\n",*p);
  ]$ ?+ s$ p* F    getch();
+ i' G- h# g7 m' A7 S! Y2 _$ Y/ W: ^; s2 M, B. U
}

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

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

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

猴子问题

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

版权声明