猴子问题

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;
2 Q* G( }4 c, m0 W* ~' m else
) {5 ^' A( C  A/ R( Y2 R) H* D+ t3 A link.nextp=i+1;8 ?3 r7 w* v" v1 I: W0 C
  link.number=i;
; A; ]% R* R# E9 G8 j}
2 O! ?% A) y3 ]8 `2 U! K5 `printf("\n");
4 D; X- j( {8 ~0 Hcount=0;' A. h7 n! |6 G( Q9 b6 d
h=M;
; ?8 ~- L8 }( ]- n" X) {7 r- ]printf("依次退出的猴子: \n");
" C" f$ O7 e3 |while(count<M-1)
2 ]' N6 Q. z; a4 e$ p{i=0;4 _# n# _5 Y! L; c% G& ^
while(i!=3)  h9 e  l* D* I  j; C3 Q/ q, U
{ h=link[h].nextp;1 Z$ m9 {/ Q* n5 a8 ^2 F
if(link[h].number)
- E- o9 B2 ?& L: x* Q  z" H5 Q    i++;}
, D  m' T, o6 g2 [4 v2 d% p; G9 [( {! z
printf("%4d",link[h].number);5 p" t, c: j/ `3 \$ a
link[h].number=0;
/ z4 [' T& \7 @, g3 r1 Acount++;3 |: Y6 R0 o" j  E" k; }
}$ m+ W1 x. }3 e" W7 d2 Q

$ l" `7 X. w" ^# Lprintf("\n大王是:");, |. j# N8 ]& T6 e/ `9 t
  for(i=1;i<=M;i++)
8 [7 \+ L* F4 Z0 v1 I8 I  if(link.number)
9 b5 w. W" |' e6 r printf("%3d\n",link.number);
" r7 J8 f3 v: R: w
; O: b. ?8 |* L/ P
* C9 l. I. `- d1 e7 j} 6 X( A! @. `, E0 ^( o
第三种是普通方法for循环
/ N0 K) D# ^( P! R( c0 w. e- C- G* P#include<stdio.h>
4 b# H( V2 Q% |1 p2 z& A! @9 cvoid main()
- g3 g+ p' W5 ]2 ~) f* }! y$ B{ int i,k,m,n,num[50],q,*p;- ^! U- D3 f' B& M8 ^
clrscr();
4 V& j$ L7 `! k! f6 M printf("input number of person: n=");) ~; @7 D9 e) k3 T
scanf("%d",&n);
: o4 f' m3 o& k4 |printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: B7 O9 V9 w. Y, L. u$ Q; x scanf("%d",&q);, ]1 s* g$ O6 P: u5 X4 }0 Q
p=num;
  K8 n8 t& m  x  for(i=0;i<n;i++)
3 X6 Z3 h" A( T5 t; u *(p+i)=i+1;8 A& X& j  I& e+ `
i=0;
) t2 P# q- L# H k=0;3 L2 i) G) s' s) o2 y7 [4 ?$ v
m=0;( k: L2 B* \& {
  while(m<n-1). O& u/ i1 p2 K* r8 C4 `7 E# l+ X
{if(*(p+i)!=0) k++;/ \* M7 ?& X) `1 U6 T8 @/ T! w
   if(k==q)! `6 g+ L" A: v% P; l
   { *(p+i)=0;
$ T8 {: ]2 i: O2 M. ~4 \+ X       k=0;) S: J! p0 X1 K9 J0 U
      m++;
- a( ]8 N$ M+ }0 z  J) ]    }
6 H- U3 N( B# ]0 S i++;
# P( J4 |( |6 Y- H; V& y if(i==n)i=0;% i" K& A6 ~. |
}
& m) w: R. L! x4 W% k$ r: ^+ E4 c  while(*p==0)p++;
' O9 _6 b' D& s printf("The last one is NO:%d\n",*p);2 m$ ~0 i( x5 C& D
   getch();. Y7 r& J& x& m& v" E

) |7 A7 L5 j3 H" r! y0 u/ c}

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

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

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

猴子问题

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

版权声明