猴子问题

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;; s' s7 }) c4 L3 e
else
, {4 g1 |# U, `: n; X/ _& [ link.nextp=i+1;
& @0 _. B; J5 d( o' E/ i% N  K  link.number=i;
+ {& \! Y7 Y* J! _}8 |7 y  K& T: d3 J! i8 x2 R5 _
printf("\n");4 w! J- B& G2 B+ i2 G
count=0;
" E' q( @9 `' S, J4 {8 \# M0 f/ th=M;
2 _) @0 Q, S0 I% K1 S6 x9 }printf("依次退出的猴子: \n");/ E" n: E5 Z, Y' N, x) b& J3 J4 u# C
while(count<M-1)
' h. k  w1 `# W0 |  Z6 Q; O{i=0;
+ V. T% |7 S1 X! Swhile(i!=3)
; ]+ K1 i" o6 \7 D7 `{ h=link[h].nextp;  c7 @- O' Y/ v" g% x
if(link[h].number)
! q8 e0 {* z9 Y5 P    i++;}: X" h$ M+ X4 x: A% C- ~; ^

4 S- ?$ _9 {0 E8 aprintf("%4d",link[h].number);
% M5 }+ G5 x6 h- e  n+ Olink[h].number=0;- m: z" B- E5 u# E9 r5 T, v" R
count++;, ^3 ?/ |6 Z& T; n$ S0 Z( G
}
) D8 h" C" I- l9 V( F( a2 v% _# a
printf("\n大王是:");, E0 ]1 Y3 J: w! h- ^$ k9 s) l
  for(i=1;i<=M;i++)
! K% s; n7 Q+ s* f2 }% U  if(link.number)
9 d0 _6 w5 D3 [+ q) M printf("%3d\n",link.number);+ ~$ n& [4 _" Q
  `$ ~2 P" Y1 q1 M
2 o+ O) \9 ]2 B2 F& C5 A- \
} * u6 G6 u4 p$ L! b6 t
第三种是普通方法for循环
' T) ?4 y2 @9 j: _, S6 F; v#include<stdio.h>
6 _- D0 z7 Q6 y$ uvoid main()+ t+ H0 Q& X' f* b; n% C
{ int i,k,m,n,num[50],q,*p;
# a- e3 A' u0 W6 t) T. ~ clrscr();* }, o* Z$ F& S9 H+ ]7 ?3 `6 q
printf("input number of person: n=");
# K7 x3 X) q( N8 `' a. c' s scanf("%d",&n);
/ J; O4 E( Q. Bprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
4 t2 h% |0 b7 c" Q scanf("%d",&q);! P: Y( o( W7 \# V
p=num;
4 n: x% C+ c: ^, q( ~" p9 [  for(i=0;i<n;i++)
5 ^2 ^) \8 i+ A5 ?9 N8 F( c% v1 y( X' @ *(p+i)=i+1;
' x, b) J8 L2 }( x: f i=0;
: O9 O7 H" E# O; k7 r& M3 d k=0;" a' @( V+ j, q5 e; [; K8 g0 [
m=0;. j' H3 @; q. S% \* _
  while(m<n-1)& Y" }/ [$ W/ w: T8 t: K5 \
{if(*(p+i)!=0) k++;
( X# d  x) [0 L) R$ D! H( t    if(k==q)/ r6 t. F, D' i& Z* g
   { *(p+i)=0;8 i, y" ?& f3 m2 q# W0 f
      k=0;- ]* r% H- ?0 Z  B7 f) L
      m++;  K- S  Z. ]- ]
   }# V9 W/ N7 g9 f5 Q8 k
i++;
% U/ n+ Q) D+ D4 ^" R0 }) r! e if(i==n)i=0;% o3 x6 ?% f, L5 l2 l' B) N* D
}' f1 D  ^1 h: m$ X
  while(*p==0)p++;( x3 y) \; ?. ^4 z( r$ h
printf("The last one is NO:%d\n",*p);$ m' ^( z& N' y1 w( |
   getch();- P$ N" b# @/ k' I: r: v! v

1 q  [5 ]) ~; T: @' X, a}

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

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

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

猴子问题

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

版权声明