猴子问题

HACKER · 发表于 2011-10-2 03:45:38

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

您需要登录才可以下载或查看，没有账号？立即注册

x

大家好!
这几天我在忙着编一个问题,我用了一种方法编出来!
但是当我编完时我去看书! 发现许多的方法我看了看,拿出来与大家共享!还有附件哦!
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激

                        题目
山上有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;
# q( S  G  k7 ^2 N else4 Q& G# C* R7 K+ {5 }) `8 m$ }* H
link.nextp=i+1;4 J3 \: @2 A7 Q
  link.number=i;4 p" i8 @0 }1 q" O' `
}: r$ v  e1 `8 L' I
printf("\n");
$ \9 S" _2 Q! v9 Y9 rcount=0;
& c7 K+ X5 j& Ah=M;
* M1 v5 I' z. V- iprintf("依次退出的猴子: \n");
* A& K! q% B) A& q/ O. G$ ?3 Hwhile(count<M-1)
8 S7 e  }' ^" u& t* o2 T{i=0;, [! Q7 w/ V0 r; }" {  T1 z
while(i!=3)
( ?6 }' V* e4 ?9 g# E{ h=link[h].nextp;
8 p, z5 K. h5 Z6 N  q2 Y if(link[h].number)
/ R8 I- r( N- z# V: i9 Y    i++;}$ F8 Y  s9 b+ N
. _; v# f+ }  y/ Z
printf("%4d",link[h].number);
4 ~/ b7 b  ~$ G- Mlink[h].number=0;" j/ U# T" v) v! }$ n( u3 Z
count++;
, d" B6 R  `; L8 A1 H}3 g# e  O, [+ M" s) U  p0 [" ]

0 @; @. A( q; h* @printf("\n大王是:");- B3 ^% P) s: Z; k- @
  for(i=1;i<=M;i++)- x1 Q' R  H! F- p  ]
  if(link.number)
8 o; x- h" c! w  h( o printf("%3d\n",link.number);6 B# a$ P" G: T; S( O+ D7 j

! G* k; B$ I' J6 t+ ~$ B  y3 ~* D7 i. K7 Z# }$ G/ p8 \
} + m2 J' X% G  F+ p( V) n
第三种是普通方法for循环
% i3 ]+ O. r- ^2 E3 I#include<stdio.h>
/ s- R8 M& A9 s& Gvoid main()
7 U0 U/ a6 S0 G) ]. o+ `{ int i,k,m,n,num[50],q,*p;5 D3 c$ r( g9 ]2 D
clrscr();
" Q2 E' w7 t" v& F printf("input number of person: n=");
+ V. o& x  Z9 E  e scanf("%d",&n);2 r' t1 t; _: ]' [1 M
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只/ h! Q) v0 x2 [8 f0 g
scanf("%d",&q);
( e1 ?: r9 A7 U% J# y p=num;3 W0 ]! D) Y2 M/ J5 q  {% x# k
  for(i=0;i<n;i++)
. o: C% `% z8 V- I *(p+i)=i+1;
! Z4 O4 d; p' I0 N! T% C+ l3 J7 s i=0;# b6 R; y# l9 R. \% J# M2 [
k=0;
. E: ]2 K& j- l m=0;
; y, m8 o. c. ]  while(m<n-1)9 y, D3 `. D! c( A  N5 {
{if(*(p+i)!=0) k++;
0 \) u& p& q7 E    if(k==q)" l2 c; M0 ?- n
   { *(p+i)=0;2 {& n- N! q6 J; b/ e) A
      k=0;- e3 D4 \/ g+ X6 k* [( K
      m++;
5 Z5 n4 {# Z. G" A, b+ E( J$ Z    }, S2 E: G5 R+ d. q$ }& m& W* o
i++;& O( q+ K7 {" Z5 \
if(i==n)i=0;
/ y* E$ H7 C+ _# ]5 H }4 A9 ~$ V" E1 S1 _6 g- o
  while(*p==0)p++;
& {0 x# _$ c: W6 f8 J* B printf("The last one is NO:%d\n",*p);
1 ]% R' a! {+ R2 ^    getch();
$ h! \2 U) u0 D& \; U, `6 v
' z6 G9 `& j- Z}

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

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

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

猴子问题

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

版权声明