猴子问题

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;" W" E  ^* K& j3 L& t: i1 l) J
else
, o7 [& M% Z7 J" P0 h link.nextp=i+1;2 H: X( F  i: ^6 Y( B4 b1 N3 x
  link.number=i;
. H) v1 [5 h/ v- H}4 D1 o! M/ V; v4 m' [2 ^7 h5 m
printf("\n");
( j4 N! ?! x+ ]: I" S: acount=0;
# I. u- j/ @# Y* }6 ]h=M;
1 C3 E4 c6 O1 ]& s& Fprintf("依次退出的猴子: \n");
2 o! k  s' k6 B9 W1 b3 P% j- n1 vwhile(count<M-1)
5 d, A& m4 a5 E" `0 p{i=0;
: W9 y) y3 x* Z9 r% X! V. e3 }while(i!=3)
& _' r+ E( |: G6 K" \{ h=link[h].nextp;
& s) t& R9 X/ P1 [2 P if(link[h].number)
0 m  f2 Q( H. n* d, \2 y& i    i++;}
9 ~+ i! Y8 y. d  h" {( a
5 E6 A( i" {! u% k, l$ }printf("%4d",link[h].number);
& b- n. `' V& Q* _/ zlink[h].number=0;" u2 I% P0 F# |" b& ^7 F/ v
count++;
. r0 h- H7 V  J; Y8 a}7 t) x! r$ |6 p6 R

# g8 _: M3 b* C" z3 Zprintf("\n大王是:");
# L# z) a1 j+ Z1 k/ ~0 m6 c4 ~. y  for(i=1;i<=M;i++), _% ~+ K. D6 K$ \
  if(link.number)
7 _# ~6 n( v; ^% u% y) j. |+ p printf("%3d\n",link.number);
$ O3 ~3 y9 h" H1 f& \, H1 s$ T
: y+ ?( E) l8 R# K: E
9 l4 C/ F7 u. E, c}
# i1 ]) E& o6 |3 _( l: h) A第三种是普通方法for循环
) w  V% p0 j( |$ c7 [$ u% J#include<stdio.h>& T% T* _1 k* Z1 o, e1 `
void main()
& A+ s1 t% d  {' O{ int i,k,m,n,num[50],q,*p;
: D7 S# G2 f0 ` clrscr();
/ ~) M. M! ~$ l printf("input number of person: n=");
9 ]  y' s& |$ j7 q! e scanf("%d",&n);
0 D- w+ k7 _' Aprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只! M* P; Y8 R" e) C3 u8 m% H
scanf("%d",&q);
$ g( V& @: A! G  c/ y5 j p=num;
) f1 _5 }* k  r( S! @; O  for(i=0;i<n;i++)
! E2 x, S, ^/ m* M/ q6 [, q6 c *(p+i)=i+1;8 A3 k' i- [8 d, G
i=0;% K8 x7 [' b# \' @9 E
k=0;) N. F% _3 ?- K- {% d
m=0;
$ G& R: A  r: e" b  while(m<n-1)$ {# J/ k( e9 E2 B
{if(*(p+i)!=0) k++;+ B- g! Q- b1 k# a8 Z9 n0 R
   if(k==q)$ c1 j- }& D) \; F* O" }2 F$ `
   { *(p+i)=0;4 S6 }/ c1 l+ I6 n) @$ k
      k=0;
! B! c5 [. F: x1 Q6 g8 x       m++;4 Y# ]! J2 P3 q0 T+ w  k) ^
   }3 E4 ^% G5 Z5 m( k
i++;) j- h  }3 x% l  T  w& Z
if(i==n)i=0;- m) j2 ]4 C! r. s! g
}
) K. E% o) T% E. u, g. G- X  while(*p==0)p++;' w# ?9 f$ Y/ h8 ~% W! M$ a
printf("The last one is NO:%d\n",*p);
9 n4 F' i# K5 @8 ~  i# h/ h' G6 Y    getch();5 @, H# \" e' o3 A7 \. e* q
" l: C  h4 }, F: E) [- {
}

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

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

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

猴子问题

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

版权声明