猴子问题

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;
# H9 b  t6 c9 `% J1 g else
8 X3 g& Y$ u( T4 f link.nextp=i+1;
- Z7 p) W3 y  d: P  link.number=i;+ t8 o5 M6 k$ n& J) K7 ]0 U
}
1 K$ J: n8 k+ M) ?0 X. Q1 g3 H/ _; Oprintf("\n");4 C% E( I" F, ?, L2 W* ^
count=0;1 Y) a+ K, g  s9 \
h=M;. ~7 E, R! I% \, c& P7 n
printf("依次退出的猴子: \n");. s5 Y# L& \& M2 B: h  f: O0 r
while(count<M-1)
4 u5 c7 `/ H. X3 o9 K{i=0;
2 ~/ e0 s& z, P+ O: i* G0 Qwhile(i!=3)
$ e- s! @: \7 a- n5 ^% D' h{ h=link[h].nextp;
4 s5 s1 f5 d% X; C* I% v) e  ~ if(link[h].number)
  j$ x' z2 j3 c  D/ ^" U/ Y    i++;}
+ `7 u. k  ^" X* w
+ J4 `5 o6 p  f3 J! Iprintf("%4d",link[h].number);2 j9 J4 m5 G+ ~& J4 b) {# s
link[h].number=0;
; \; k. D: `3 t7 l1 Z7 ^& I  xcount++;
/ v7 O3 e" @: e- v, t& b2 s}
' H6 q. Z& ]1 \: v0 Z
/ `& s6 Z: r: R9 e0 B( fprintf("\n大王是:");
8 V/ ?* O/ [: D% U6 a  for(i=1;i<=M;i++)/ d& y" J" y! j# \0 r0 H- [/ B
  if(link.number)- P4 A1 ?$ @* K' b/ R0 m  R! \
printf("%3d\n",link.number);
! o; `7 g- l; R  }& \5 v
) \- \: ]: }- d! X9 e4 u, ?
9 _& n! T, Q4 g5 Q5 C) H% `} 1 X/ `: W" M! P) P7 c8 `/ m
第三种是普通方法for循环
' F, z8 c& e9 c, S' k: U#include<stdio.h>
# ^# B3 ?4 f2 x- J" j5 I8 q! Q) svoid main()
4 ~2 G% i9 a3 h* L. S; y{ int i,k,m,n,num[50],q,*p;
9 {# C9 X3 z4 j2 V6 s8 w/ [ clrscr();+ @$ d8 v* c1 E6 T
printf("input number of person: n=");& z7 Y) W6 V2 `- }+ _
scanf("%d",&n);9 M, N- V8 t" J
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只  @" B! K9 ~. i" ?
scanf("%d",&q);
8 j& g* g. C& P% d$ o p=num;
- V  V0 E# K6 D2 q& s* W( V  for(i=0;i<n;i++)* m1 f) d. y3 c, J* f
*(p+i)=i+1;3 b7 K% W& ^  U4 y0 l- S4 n" }$ z" E
i=0;
; M* B# _6 J' q6 N) K1 H* j k=0;+ R" X' z% A$ z. J+ f
m=0;
% [, J2 Z0 ?: Q; z$ E9 J  while(m<n-1)+ _/ v/ H* z, s8 v2 }1 |3 {
{if(*(p+i)!=0) k++;% v, D: ~" m* r; `6 v$ a2 n7 C6 E# x
   if(k==q)
/ `3 Q: }. p. c3 J! `    { *(p+i)=0;
8 }5 a9 B4 u3 a1 w3 c       k=0;
1 u" `/ v8 P+ v. v; E       m++;! n5 {$ A  z/ X" B( J& Y
   }# A5 {- b- b9 Z4 T$ Z# k3 C
i++;  O; c8 O% ]6 f( Y9 F9 G
if(i==n)i=0;- S, Y; x' b- _$ b2 }1 D
}
# P: I  v& I$ V5 Q# E4 d  while(*p==0)p++;0 ~7 A( J( ~& e1 `
printf("The last one is NO:%d\n",*p);
4 p) a$ M2 E4 v/ I' ^* g    getch();8 Y, d" E: h2 l+ D  ?& A

6 }! ^6 J' p# {! z: X% k}

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

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

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

猴子问题

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

版权声明