猴子问题

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 a: M6 A- ~% k: B0 H
else; Q. s, a" c0 L0 ?
link.nextp=i+1;; T) e5 Y1 j  Q) k
  link.number=i;; X9 V% Y& w( Y) _/ U* c
}1 I3 a' j/ e, g% s7 g: B) ]
printf("\n");
; v. U  M/ t' C( Xcount=0;0 ]+ ~1 _8 N5 Y
h=M;
" M1 F$ s% a- F5 W1 vprintf("依次退出的猴子: \n");. ~  C* ?' Y" g: h0 b, h# j
while(count<M-1)
% m* Y+ e( |$ m: v$ v, S) u{i=0;
9 }$ S! Y6 i9 V& ~) B8 Awhile(i!=3)5 x  \7 h2 r( f- S  @# h
{ h=link[h].nextp;" D" I6 D( w: n8 V; f$ ~) o* F* W! P
if(link[h].number)
2 b! @) W6 \& ]& s    i++;}
! o# O- m' o6 T, m8 h9 l. F- N, G: m, ]
printf("%4d",link[h].number);
4 s" s9 Y' ]3 E: |" i9 ^link[h].number=0;
8 V8 \: O; X  ~; }) k  kcount++;+ X; t! o, z8 Q; M2 I
}( w1 Z+ L6 d) W
2 B1 x/ Z% }  ~% g. F1 w
printf("\n大王是:");4 `& Z/ r, ?& w5 V+ e4 Z
  for(i=1;i<=M;i++)
2 y) B* I* I1 Y  if(link.number)
) m; c  h' a" N9 W$ B% X printf("%3d\n",link.number);) `% R+ _; {, p( z
) ?4 b: G9 I& z5 O8 |  w
/ \) v: m5 I/ u' x% ^- y
}
, v. S' Y3 n3 \# O% D第三种是普通方法for循环1 U& ]' J3 a8 H0 z2 P, c0 v1 N6 f
#include<stdio.h>  ~1 k! ^  Y$ p- J  C2 k% u5 @+ T
void main()
3 M8 R! M4 t  z9 d9 t{ int i,k,m,n,num[50],q,*p;! ]% ]: w) r8 k; Y8 w
clrscr();
1 J+ o1 z- r7 E9 \ printf("input number of person: n=");% |: N8 E+ O$ P+ a. j- }
scanf("%d",&n);
% [1 J( P1 T& d0 B7 kprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只6 S" z% i5 r( \9 }
scanf("%d",&q);& d6 z) ~0 _5 W# w+ N3 X
p=num;4 W* v0 ~2 K4 E& A7 j
  for(i=0;i<n;i++)0 n9 s1 X- k& q2 E3 K6 {
*(p+i)=i+1;
! r  \" A' _+ Y/ p- J3 @ i=0;# ?: S. t$ `- T: @2 q) F
k=0;
$ U  T8 q9 }* v4 D m=0;3 B4 U. A/ x* L5 v5 J
  while(m<n-1)$ k+ s( i$ L  P7 F: u: J7 l+ `: B$ W
{if(*(p+i)!=0) k++;6 d9 f" W. @: Y8 }* Q; b  \( g
   if(k==q)0 q8 c0 H! e) G1 D
   { *(p+i)=0;+ }# n1 x; W' V2 a
      k=0;
9 K" F3 s$ I7 Y  W* L/ I       m++;
0 z% ~& q# i; W# Q, r9 [% J+ [/ H    }
4 x$ P% I+ z7 o i++;
; W  U. v. {6 J if(i==n)i=0;! t2 W- }8 F% g4 x
}
( F$ \  R0 {& {$ \  while(*p==0)p++;
5 h- x, M- [6 R( j* c/ b) C6 A printf("The last one is NO:%d\n",*p);
- f  N5 m) K! o: E/ f* l    getch();  m- u) N' {/ l) r

9 d9 u/ O$ d9 S  W! z" Z8 y}

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

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

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

猴子问题

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

版权声明