猴子问题

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. J5 i, ^! L- h else
7 I4 S) J( e3 p3 ` link.nextp=i+1;- @0 N- f' F0 y, `1 ?- g
  link.number=i;
5 E. U, C# C4 Y9 T5 J$ W0 w}
, a8 M8 n& G5 p( v. G" a. f/ lprintf("\n");
5 q5 f7 l) U) Ocount=0;
6 @5 n! @: c. N2 O* k0 `2 Q: Qh=M;' Q1 S( [8 c3 d9 |$ L+ p
printf("依次退出的猴子: \n");2 D/ O1 q6 x) f2 w% B" z0 F0 V5 X
while(count<M-1)0 T$ z% F! v" g7 G3 E, |
{i=0;, f6 n5 x$ A) b$ [; M; a9 {
while(i!=3)2 X2 E: {, \* w1 D! t$ m6 q- o
{ h=link[h].nextp;+ {! b' z- Z; [! M  v! b8 G/ o. M
if(link[h].number)
& ?+ q6 G2 i, h( y# e6 O, F    i++;}' ~' q! v/ v' _7 j. h

# f/ D3 E( k7 _$ Hprintf("%4d",link[h].number);3 c1 S& l- K: q' z( F' A# r
link[h].number=0;
$ @1 U+ Z; W1 y$ q6 V# N5 Ccount++;
9 ~; r8 ]* V9 c* x! l6 [}  }  k4 G: x" k6 t0 U

4 N5 u, I, W+ Q, uprintf("\n大王是:");* i! @. O, {' ~' f5 y
  for(i=1;i<=M;i++)8 s7 l$ Y6 h* X5 `0 {# P
  if(link.number)7 p- Y# n" W6 Y  W3 H% h
printf("%3d\n",link.number);- F! n4 @) j! N* B' @6 r

* ?' q; H# r+ K( G# R
# Y2 F8 T1 R/ u7 w! J} % q0 y' L3 ]6 w
第三种是普通方法for循环
#include<stdio.h>) L7 V1 i2 U) b' t; A5 b. @! [4 X+ h# W
void main()# Z: i  A" Q0 o+ U/ j
{ int i,k,m,n,num[50],q,*p;
* k9 g' [; e- d' x* J clrscr();
, i9 a" ?; `0 K+ ] printf("input number of person: n=");
( e4 q: o# N' @ scanf("%d",&n);6 R% a8 S8 c2 p) |7 ^' U
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
9 k! `4 e9 [: p% X6 X scanf("%d",&q);' r0 ^( P- {) L
p=num;, [; c( M1 {  m! l" B1 }0 e
  for(i=0;i<n;i++)% x/ d% l7 z* r% Q( m! h- ^- U
*(p+i)=i+1;
& [. a: B, Q7 B3 K- _% ~ i=0;0 m' D* c9 D+ Y* n$ X% M
k=0;* K4 A6 W/ c7 g" j; T2 K
m=0;
& S1 A: f' F" \5 b  while(m<n-1)
# y5 W7 D3 t& _2 G7 P {if(*(p+i)!=0) k++;, q; I! F5 w8 V& Z1 o  D7 h
   if(k==q)
8 O0 N' j( `; F4 v    { *(p+i)=0;
% d' A5 N& _7 [# Z* ?+ Q' O& ^       k=0;7 l; ^4 f% `7 D, S" J: j  H
      m++;6 C) t* O- Z# ?8 U4 S  Q
   }
7 a9 M: Y' ~- c6 ~ i++;
$ Y6 L/ f, f3 }2 @ if(i==n)i=0;
2 X" E  X0 r8 e. E% D1 O! i- ~ }
& Q" G2 A. U+ c( v  while(*p==0)p++;0 n; Y9 x) [; I% ?* E6 D" [" y
printf("The last one is NO:%d\n",*p);
& S' Z2 X; O) Y6 R    getch();
2 ^! e& `* H, v$ `6 p
% _4 A) k9 R9 K$ R}

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

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

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

猴子问题

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

版权声明