猴子问题

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;% H- O. V# |8 n' p) U* E8 u
else7 V% Q0 K3 g- ]7 P3 H0 A* c
link.nextp=i+1;: x) T  i7 x2 h! u' K' `
  link.number=i;; n! t7 v4 u8 g
}  p2 M! Z( H4 _/ u' d8 W7 E
printf("\n");) c' J0 i; r; \3 H
count=0;
& E  Q) ]. C0 Ah=M;* Y, G; F: V2 P6 c
printf("依次退出的猴子: \n");
5 C. Z# m( d7 N) c' [while(count<M-1)4 {5 [) ?9 f/ b
{i=0;
$ S4 L3 v. J9 x# M6 H  E4 Cwhile(i!=3)9 N8 o; J$ {  Y+ p- d
{ h=link[h].nextp;: I# z. O$ m( B! T% K6 f
if(link[h].number)
2 s# j. L8 H6 e( p' P9 n; `$ x4 S    i++;}5 V. n7 M0 |5 F. J  W
% _. T9 {' h3 h5 J0 X) G- I
printf("%4d",link[h].number);
3 O! I+ N8 Q! y; Jlink[h].number=0;3 {! I/ Q/ S$ M" @* ?& V& A
count++;
/ [2 g' M% T9 f% l5 D/ n}6 g- u& ?0 y. N' Q3 ]
+ F  P  `: j7 K4 i1 H
printf("\n大王是:");
/ m9 S2 V0 I# ]) i5 l8 j0 c5 y. a  for(i=1;i<=M;i++)
( J# I0 {) k5 C0 q) G  if(link.number)
) ]; h+ ^$ M- U% q& U printf("%3d\n",link.number);3 D- B2 |- |$ t) b3 N* W

( \0 ]9 ^( P% k: n  S
) }0 d1 [( S* i3 _3 o/ u( J}
" y4 z$ g1 n1 Y) k# j, p- }第三种是普通方法for循环
$ P) o: `# z7 H: {; r#include<stdio.h>
3 a' d# B' I$ Qvoid main()
# W+ ?- ^1 d8 V. m' m{ int i,k,m,n,num[50],q,*p;0 @( Q9 z$ [. k' d/ R
clrscr();7 j% z4 w4 Q4 `% g6 S5 ]
printf("input number of person: n=");% ^+ M+ F4 `1 K; r0 _
scanf("%d",&n);# Y; n& J4 V3 O
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# V' l5 c' V- q& N$ I7 j2 J scanf("%d",&q);9 d* v7 Z, ]# c9 o" X
p=num;
- G) B0 d# S, f  E) P  }  for(i=0;i<n;i++)
. L" {- N) ?6 S. I& z0 X; Q *(p+i)=i+1;" [. C4 V5 L& _" ], g/ H- W8 B7 Z0 w
i=0;/ E( e' u: K# s1 _3 B& F9 i8 s
k=0;0 `6 ^% K+ \, x
m=0;
# c7 r$ C- E1 N/ j  while(m<n-1)( i/ l1 z( g  X" e4 z9 D, J
{if(*(p+i)!=0) k++;) ]( X6 Y. j. y8 ~" E6 {
   if(k==q)
7 F) q- g. m3 q8 p8 s8 h2 ]% \" I0 V    { *(p+i)=0;
4 \# w/ Q3 p) U/ `& u5 g       k=0;( W/ |5 H2 Q: J( _9 J
      m++;$ G3 f8 ^: w9 N3 K* E: Y. O& ?- i
   }, x- f) u( N; }" ]* B7 f. O
i++;
9 k/ V8 Y+ |- M if(i==n)i=0;. F' U5 A2 L% [3 U, ]
}
6 v& {- T6 L" f2 P) u  while(*p==0)p++;+ F+ ^* M& m, p  e$ \
printf("The last one is NO:%d\n",*p);
" M7 N! S/ Q/ k$ u$ N    getch();4 O" r. }7 i, ]# U7 z0 a/ Y
$ s) T8 i% K$ t6 G3 C) D* v
}

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

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

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

猴子问题

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

版权声明