猴子问题

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;# }! N, {  V( D6 A: b
else
* `; T6 \  C$ l link.nextp=i+1;
$ x" x) n. D" U0 R* n7 Z  link.number=i;
/ C6 ]2 i2 G1 z}
. l) H2 ^/ I. M2 C2 v) E7 E; z4 Jprintf("\n");5 n* {6 s7 G% O9 P# s2 J
count=0;2 m! `/ U& R) Y% I7 z" d  N6 I
h=M;
* x2 i# c7 M4 {* o7 oprintf("依次退出的猴子: \n");9 v/ x$ c( y+ E9 ~" S1 H1 \. v7 c
while(count<M-1)7 p3 X7 ~3 }- x* H1 E
{i=0;
% L) N1 D3 y4 O: c7 T, h( M  ^while(i!=3)2 y& e7 X: g) O! p9 R& F9 @& O
{ h=link[h].nextp;
, C6 T! P1 V3 T& w) p1 S  _ if(link[h].number): O4 T4 G& F# K
   i++;}* ^: |* |, [9 A/ {
3 d' G. I) R3 y& S! H
printf("%4d",link[h].number);
6 Q% f. A5 ^5 c5 |; L8 Wlink[h].number=0;; ]8 `) w, J+ f
count++;* L4 D9 T% \! A1 G
}
  D9 o. X2 r1 t/ o# p3 b- Q3 {% M" y( a- l& S0 D3 d
printf("\n大王是:");. W/ D) U7 X  i: |) \. c( b
  for(i=1;i<=M;i++)
# I) N( j- G. ]$ p2 {! ?' D  if(link.number)3 Z5 P2 Q9 j- R( K1 r
printf("%3d\n",link.number);
! P5 m- y# _3 v2 w* I
# @: d" e( T; X. j  Q
/ v% _- a4 E6 V' s% J}
( q" E! ]% I: Y第三种是普通方法for循环" E5 X# D2 @6 \8 ^2 Q
#include<stdio.h>9 A+ Q* u5 x8 f/ ]( Z
void main()0 A# ^6 ~( n% V0 g. @
{ int i,k,m,n,num[50],q,*p;
; _/ v1 k& f  q8 { clrscr();
% D2 Y4 L: X' Z9 u$ m printf("input number of person: n=");
' h3 l1 G0 d- V! Z, Z, X scanf("%d",&n);
' i: A0 q) g. X3 f3 ~  D% hprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只( \- _/ a" s' t; Z" y
scanf("%d",&q);
6 u* [; s) `1 w) @6 Z" p p=num;( _; E8 K( s" }& f& @4 `
  for(i=0;i<n;i++)7 V! ?4 B) a+ M& A" ?1 X+ [
*(p+i)=i+1;
$ e5 o( d( D# ~- b1 N) E i=0;  @- w! t" ~' V5 d7 g0 J
k=0;1 i6 s9 T6 o4 O% w
m=0;
1 S6 F) G( J' g1 q' L6 Y/ k  while(m<n-1)9 e  o) |) j9 t) ~5 ^+ \: h
{if(*(p+i)!=0) k++;
4 P8 a- U3 L) W  R' K1 ?' Y    if(k==q)4 h; F; {  h% j" w
   { *(p+i)=0;( T! v0 C9 T6 ~9 j: z6 k
      k=0;
' L+ p2 y- K) |       m++;
8 C' D3 Z+ q' k: t1 U# F    }% A2 g! D; b0 N# a
i++;4 X" y- F, S; B% O) P. O' n
if(i==n)i=0;
* q8 N* ~8 ^  f. B8 @; n& Y$ _) ` }
! t" g& v: |8 J9 R" Y# _4 g  while(*p==0)p++;, S7 n2 @; F) p: q) Z- B' p
printf("The last one is NO:%d\n",*p);+ T/ j. L! D' e  k" ]& {6 c
   getch();
# o- M( j* Q3 ~$ G% o# g% |3 E& y1 z# ]. ~3 u3 \) T1 H- o( S
}

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

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

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

猴子问题

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

版权声明