猴子问题

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;
3 \  S+ V$ Z4 _* ] else# \& _) h+ P" }# r5 q, d" A# ~# E
link.nextp=i+1;
, }# M7 d4 o3 Y+ S3 T  link.number=i;
& K; e/ o1 {  t5 V& s: ?}
4 k! N: g, M( N0 g5 B1 b( c5 eprintf("\n");
+ h3 _! `3 |$ [- q! k4 ncount=0;
8 ~$ r3 o/ m, W/ B3 n# M  k3 Qh=M;
% x( @6 a, n/ J' ]printf("依次退出的猴子: \n");
/ I. N# K( G+ \+ r/ ?+ l/ Mwhile(count<M-1)
, @6 {* y" B" g{i=0;
3 y  A/ C# F2 Z' rwhile(i!=3)! @6 J7 y+ V; D: v9 X
{ h=link[h].nextp;
7 R0 i+ \; A$ N% E" u* T) ^ if(link[h].number)
$ d7 u( a* ^, C! H    i++;}
4 ^" Q) f9 ~0 r4 W9 O6 u  ?, R1 a6 s+ O6 E/ t! ]
printf("%4d",link[h].number);
8 q- B5 s) e: ?" S4 u* hlink[h].number=0;
/ H- G4 p& |6 e! Kcount++;
+ H: q! ^+ p" Z+ ?0 N- C}
# C- p5 g$ Q6 @  m
2 \6 m" R" q7 ^4 pprintf("\n大王是:");( E: d$ J/ I# T$ j
  for(i=1;i<=M;i++)
3 C0 |+ p. {' M  if(link.number)& G+ F: w" C' I
printf("%3d\n",link.number);9 c; w$ U' [: ]: g" I
7 [4 M1 M/ [9 l& L' ^) s: R2 p7 U
0 ?: Z: N7 C: \# X0 l$ h4 B
}
3 O! Y9 ~4 Q7 l& T# L第三种是普通方法for循环" Z: \/ i: p) c8 e) d
#include<stdio.h>
; V  x& {% C. L2 P# W9 v8 bvoid main()# t* x; T9 b/ C2 X
{ int i,k,m,n,num[50],q,*p;
  m9 s# D0 Y! C* [3 K2 I( l3 p0 h$ B clrscr();
6 \2 B- j) I; D  O8 a printf("input number of person: n=");4 }$ b- O' S) h) `" ^
scanf("%d",&n);
- e+ v, u8 y% y+ v/ c& Y  [printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% e& x: D1 x* ?, D/ g; A
scanf("%d",&q);
) W, K8 }9 a: Q" Z2 A0 ?& | p=num;* p/ o8 y7 h$ `
  for(i=0;i<n;i++)* H8 i' \6 ?' n5 z
*(p+i)=i+1;
: F; d3 G6 A+ D% Z i=0;( ^) t: |9 X- q& J$ j* A
k=0;: U+ p& Y$ e7 G: Z
m=0;8 B8 d2 z* T! r# ~& T0 `" ^
  while(m<n-1)
! R( z8 |( [8 O4 w/ ~. K {if(*(p+i)!=0) k++;
3 R2 @# e8 J9 Y; S1 a    if(k==q)
) `! R  R7 {* L# [0 s$ `# `" |, K    { *(p+i)=0;
* K* y, X2 o- x3 U2 T3 \0 g       k=0;
* t( ~/ R% ?3 ?* b$ {       m++;- R" A) T) q, |0 }; A5 G
   }) y- w* i& {4 l( R; e" a7 g, b
i++;
" l' T& x4 r) b3 c. z- I/ q# k if(i==n)i=0;  v) W- u! n1 I+ ^0 Y
}
1 `5 d- @1 D6 _% v' a6 S3 E  while(*p==0)p++;
5 P9 N" _* k5 [' y printf("The last one is NO:%d\n",*p);' u: r+ S' Q5 D* ]+ i6 R
   getch();
: ^( W8 `# k. Q& a+ o3 A
$ P% A2 P: z- P# F# d% {}

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

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

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

猴子问题

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

版权声明