猴子问题

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;
) ~' o# Q' T+ B4 l! b; s" g else
* E! r5 P1 w' x link.nextp=i+1;
1 J9 }7 k6 `' b: k) |  link.number=i;
& d, _$ S+ u1 H! ^) r+ a}! J: `6 g3 o% j
printf("\n");; N1 [2 t  ^" c: E5 T
count=0;
6 ?- ?* o* i' j/ X# k9 oh=M;
, I! Q& f3 \9 ?" e1 B' ^printf("依次退出的猴子: \n");
. s* i5 s( Z1 Z# i, Mwhile(count<M-1)- m( @' K  m$ {0 A/ e6 X' [8 V
{i=0;
9 O$ Y( }8 C  L9 uwhile(i!=3)
9 {6 a6 a8 W& \5 U& B' [4 I7 a9 P4 @{ h=link[h].nextp;  A/ s7 Q1 i  x( r0 f1 Z& g8 Z
if(link[h].number)2 y0 c5 i# A2 }( M
   i++;}
; }' s+ @8 `6 ~2 K8 A6 r# j
$ T0 ~1 S+ m5 _1 h# Qprintf("%4d",link[h].number);# f: ^/ Q$ ^/ d
link[h].number=0;( r3 U" l  }" i4 G
count++;. [9 a8 @* K  i- P
}  G) q9 l! z7 j; d, o% r
* Q% z) a6 j9 f; ^  A
printf("\n大王是:");' O  q, w/ s% E0 k
  for(i=1;i<=M;i++)8 E, n* C3 Q& h5 C  h
  if(link.number)
6 W( a  ?! x  }4 t- z; I  w: b printf("%3d\n",link.number);1 u0 I% M3 d1 A3 t) T3 j" l' s
( {2 h3 @( x% ]- j5 `4 ^, Z! t; `

0 b' z1 e: I, d! f/ o} ! V8 B$ ?  b8 s
第三种是普通方法for循环$ R. t. {2 y% K6 e) [
#include<stdio.h>$ m$ O% N; L4 b" v7 q1 H" ~* A4 k" |
void main()
* m! s9 e6 q% ~7 x; z) r  |{ int i,k,m,n,num[50],q,*p;
& W( }; O) L" J clrscr();, l& {& W) w5 S$ \7 ]# R/ ]
printf("input number of person: n=");
) C0 i- H! c' @" c scanf("%d",&n);
6 M& H  e+ v0 W1 N2 eprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
( z; K( Q& n+ e6 g6 Q" v scanf("%d",&q);- T# ^+ n  B4 S+ h/ i
p=num;" p# e9 h3 [( }4 M0 ?7 C
  for(i=0;i<n;i++)7 s- Q" ]  l- H: h: D0 q; e
*(p+i)=i+1;
) G% }. m3 A. A$ `* X( f& i i=0;) o1 C4 ~! p+ b  m; w
k=0;4 x( v- |$ ^* L$ j
m=0;8 e4 `+ K/ M) Q: E# J$ j
  while(m<n-1)
1 Y, D8 N7 p. @$ V {if(*(p+i)!=0) k++;0 {5 J' k& S0 n7 Z
   if(k==q)
! D% }% c6 @; g% T8 i    { *(p+i)=0;0 R5 d# t- n' q# A  C$ Q5 g
      k=0;; v- h- Y6 V1 O
      m++;
- M, L( A- d0 |: ?9 o$ l8 j# H9 N    }  k* R* n2 G" }' Q7 d, R
i++;
8 z- I3 T- R: S/ u3 G  ^+ Q if(i==n)i=0;
- @- L9 A" T& x4 I& b7 W }- v5 p) E0 H; ~- \5 I/ \
  while(*p==0)p++;
8 C' O; e0 v9 l& w8 a* W printf("The last one is NO:%d\n",*p);  c. _1 D' [  L
   getch();
& M) Q+ ?) o* G3 n
) Z% h9 u6 C8 @( Y/ F8 _2 h}

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

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

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

猴子问题

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

版权声明