鱼C论坛

 找回密码
 立即注册
查看: 3438|回复: 4

猴子问题

[复制链接]
发表于 2011-10-2 03:45:38 | 显示全部楼层 |阅读模式

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

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

x
大家好!! ]  P$ ?- g$ d+ n
这几天我在忙着编一个问题,我用了一种方法编出来!/ P1 v) a' i7 x5 W/ q) o
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  K  f. Y4 Q7 q! J9 [1 G8 ~注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
- T& @( f! B) i& e2 l/ E3 M/ S5 m5 E, I/ f
1 Q# ?/ y0 \& V7 s
                            题目
. g- q  m' h: W1 v3 ]4 X  G* Z" R山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
9 l+ f+ _1 |) ?* b" L7 `第一种方法:利用循环链表
$ n4 l3 X: X4 r2 g1 n/ y- X8 F0 N#include<stdio.h>8 ^: C4 q/ k) ~; }" H& C% q+ \
#include<malloc.h>- q) d- Y1 p8 }8 V' m- E9 h
#define M 8            //共有8只猴子$ V7 k# W; P' \% M$ a5 H
#define N 3            //数到3只时退出第三只
6 Q" L# [5 }% R3 P9 T- O, ktypedef struct monkey
, b# r- c- N! L7 X% S* X, f& A* @{int number;
2 m) j' a. C: Z8 \7 N- h7 lint flag;
- l/ \/ r5 X3 S$ L# Wstruct monkey* next;
  y" i/ G4 b4 H; h+ p5 T}MONKEY;
% t1 e7 J8 i% P7 t6 `main()
0 y' l+ W. D& Y7 k{ MONKEY *head=NULL,*p,*s;
' R, Q4 d- j6 h5 c  int i,sum=0,count=0;
2 V( q7 Q' u7 x  b/ \  clrscr();              //清屏
( m2 _) f' x5 a! P  t& [8 r  H  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存3 x6 {7 C2 M* j" L1 y
  p->number=1;p->flag=1;
/ C2 }, L( V' Z$ Q3 Y  p->next=head;
  R4 d2 u! ^  c$ M" A  head=p;
+ l( O" w8 X2 F& V. o  U  for(i=2;i<=M;i++): H& q2 o/ v# f# x
    { s=(MONKEY *)malloc(sizeof(MONKEY));
4 \# K- _8 V+ {- ?( R9 P     s->number=i;s->flag=1;3 {" n* [# M1 n+ L
     s->next=head;
# L- X- c8 W9 Y- L5 G     p->next=s;p=p->next;; y, f' i* D8 P! i: k' C
    }
1 S% G' s5 m8 Z; @    p=head;
6 P$ Z8 r' F7 p. z) O: ]& S- E7 @   for(;;)
. c% Y7 {* Q. b) w( l& x  ?    {if(p->flag==1)- P4 L5 Y2 _1 z3 I  U0 Q1 \" |4 [
       count++;1 W3 D7 R! j/ P+ O
     if(count==N)
4 L+ c1 u% [0 [% c        {p->flag=0;( `$ [2 l8 U+ ?( h3 o
         count=0;$ T6 p- u9 O9 v5 h& X
         sum++;}, }9 A6 _3 s% E
     if(sum==M-1)
7 Q( M" k; t7 ?4 P- d! i0 Z        break;
4 G( `  C5 B0 J6 m     p=p->next;
4 I/ V* I, B; M' u; O8 r    }
3 f- y0 j+ n$ b6 d: ?5 i& `8 Z    p=* b0 s% Q# i4 A1 U# V! h) f' H
    head;
( R2 Z/ Y0 h) C. n; \* |8 J    for(i=1;i<=M;i++)
) v: e( J  ^7 c  z- J& _& J$ i    { if(p->flag==1)
2 N) [* S8 X4 r* x2 P) @9 ]        printf("\t%d",p->number);! W) b/ A% @6 e! x4 D
      p=p->next;1 C! n% h. Z8 u! e7 ]: [
    }1 x1 N- t  f4 q: }+ k
" @" S. A% H/ q1 n

$ G, V, ~7 j2 X/ o' `8 l' i* }
: v8 B/ N( Y# W5 h}

' h" I, f  N6 }5 u# T第二种方法:数组# M" u* z2 y5 ]. M; t
#include<stdio.h>
, ~% o+ r3 G0 g  D; M$ V#define M 8
1 I4 a: a' ^! m4 ]+ n3 istruct monkey3 V7 ?% z; N( h: H
{int number;
" w" e6 W$ i( Q( b: V5 S  Dint nextp;7 S" ~$ F" c' p
}link[M+1];! t; L( M+ ?. A6 M! L6 }0 Z
; J: E1 K+ P. ]: q) z4 ~9 D/ i
void main()
. j# a& _9 \, ?: G( g/ \5 J; _{int i,count,h;. A& @9 W3 ?3 W# x+ e$ X
for(i=1;i<=M;i++)% f* H$ V7 S7 V, O" M! \4 C
{  if(i==M)3 o2 j" D8 u. m* ~
   link[i].nextp=1;
  d9 F1 ]5 \2 E$ x4 o   else
5 R+ `8 X7 `# J( w, c   link[i].nextp=i+1;4 a1 h8 X$ p+ }
  link[i].number=i;& ]$ x1 n$ x3 L+ T* i9 \3 L/ k0 j1 J
}* ~2 e+ t/ ~6 W2 A+ e8 i* a1 i
printf("\n");  M2 f/ T" W/ K0 L
count=0;
/ ]2 p- ~# N% s+ ~h=M;
0 \$ i+ E1 ?! j+ L& `% }printf("依次退出的猴子: \n");
! x' E2 d' K9 g6 N+ m6 ]( [+ ywhile(count<M-1)
) [( m) n0 c: v$ @{i=0;
2 A! m# w$ p7 o; `while(i!=3)0 v# `( `- d5 D1 U2 i
{ h=link[h].nextp;
' Z$ x! G* s8 `9 H8 L5 z# k   if(link[h].number)
$ U, H* `3 ], G% e4 |! O     i++;}% t0 V  d9 Z) [7 L
% k  z+ m& u( b+ ]! a
printf("%4d",link[h].number);) ]" {- i) S+ X; Q9 d
link[h].number=0;2 P6 Q& v; `0 t; j/ r
count++;3 H' Z& ?( ^6 ^& D0 B! G
}
( Z1 [4 E6 m8 M. D9 i$ i1 X" g7 m( O$ g& q4 q/ m
printf("\n大王是:");' Q( h- V, i: @; J, Q. W) E
  for(i=1;i<=M;i++)
. I2 d7 t% h! B) R  if(link[i].number)
4 M+ h7 Q8 x% z& H2 K+ L- r    printf("%3d\n",link[i].number);  v1 Q$ |) s' ~$ Q( c0 T& C7 n

# o/ Q  h% I5 _3 M9 i% w, }
7 h* r1 e0 t. j1 W}

! v: U$ p9 |9 f( N第三种是普通方法for循环

( N5 M6 n2 F6 _2 n: S#include<stdio.h>
2 W8 o" ~+ S: ]  svoid main()- u+ V% r( T3 C% _% p
{ int i,k,m,n,num[50],q,*p;
" S2 }+ a; r+ W" ~1 v    clrscr();: X% n' h  W2 q5 e8 `8 f; A
   printf("input number of person: n=");
& f9 y' B9 o% M. b$ j    scanf("%d",&n);
  h3 o* S" P2 r- M) Y( Hprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只5 p. t( c( H' Z& U( A: O
    scanf("%d",&q);
2 C2 o/ Q* p, p2 p% K3 C   p=num;/ z, m1 \' U& n' m
  for(i=0;i<n;i++)
' @( C- J  X6 [0 Q' h# E9 [. Y5 c: o- x    *(p+i)=i+1;) t7 w; R/ e7 {% I
   i=0;* r) W) V  `/ N
   k=0;
6 P( s0 D; w' [: m. e! ~   m=0;3 [; D7 U4 }, K* ~( A2 {$ g
  while(m<n-1)
2 n. O: D' `+ R. e   {if(*(p+i)!=0) k++;0 o" h( r& A/ H- W4 ^7 U
     if(k==q)
1 u) y$ j+ E( Q( _8 }8 {      { *(p+i)=0;* w/ H) Z" @5 Y% q( a+ s* J
        k=0;/ o: y+ `' M; E/ u0 m7 E% D* o
        m++;
8 Q/ U6 u6 J& s1 L7 K      }2 c& s/ g% }3 D2 Q0 w8 ~8 _  b
    i++;: u' B" P+ c8 a) [3 R8 I
    if(i==n)i=0;
# b" w& [; U) ^4 c2 a   }/ [! l% x  G3 ?7 @7 p. L
  while(*p==0)p++;
% ^5 H3 d; p! ~+ s/ }: P" Q1 t- A, |    printf("The last one is NO:%d\n",*p);) a" |1 z, C+ b% K4 Y* G9 L- Y+ \0 H8 J: Y5 H
     getch();
. N8 @5 X  i6 |. ]) c1 \* J8 q; B. S5 }3 L5 j
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;0 f7 G+ J* i% [9 k0 j% S
namespace 又费马达又费电  j6 q% G; A; W* B2 B! l. f4 s
{( P& s! A, W; E& b# v+ B+ X
    class Program
9 V6 Q9 f8 i( B. D8 n    {: f( B! t' ^7 |4 q7 k
        static void Main(string[] args)
# M& `% [4 I# t7 ?        {
% U) E# F' Z$ R5 f( {$ d; ?            int m, n;! x  x8 ^; `' `; |
            Console.WriteLine("请输入数组长度");2 E# W( }( ~& R* x7 I
            m = int.Parse(Console.ReadLine());//m为数组的大小1 b  `2 J( ^# G& K$ u+ G8 `2 n
            Console.WriteLine("请输入要截取数字的大小");! g9 |4 Y1 X5 d5 R4 c$ P1 K+ c
            n = int.Parse(Console.ReadLine());
' U) l# A% O# t  O& w            int [] numw=new int& E* L5 A+ F7 G) y' t& Y( u
: g" Y& l$ b3 P) b4 ~9 Y0 i
&shy;&shy;&shy;;
9 d/ i+ u4 @1 [: v* r# ?            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 Z4 y) L# y' k' `1 U0 Q. P% S' N5 R' Q
            {# J% B& I* @0 I
                numw[j - 1] = j;" j9 h- ~  _# N+ t4 b" p; S
            }8 M: r4 J! L6 g! l5 G; x
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!0 A, g7 `. ^* Y* Z& H) a" d
            while (d != m - 1)
, Z0 Y2 D0 t/ {" N! |            {
" b! g: m3 Y9 H4 V8 y' g                if (i == m && d != m - 1)+ x9 y+ b1 \* P( X  H
                {
% E/ G: j% c/ _                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!" v' f7 ~8 D6 e
                    continue;7 `& Y) a* R4 B& ~, t
                }
2 p8 M8 M& @- `; b' S! u                else
' c6 ?) Q- q8 w- m  {2 q                {! ^0 n5 y8 Z, j# e+ [7 `: U
                    if (numw[i] != 0)
2 W/ t4 q! D$ E* k7 {                    {) A5 z  \: o8 d+ Z
                        i++;1 _' a3 l; |5 j& e
                        k++;
- m+ `8 ?4 v' X8 X                        if (k == n)
# k  u' Y* o4 T( s                        {
! E1 p9 E) h* d7 @                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
) v8 T- B' m- r" o" G9 G- _                            k = 0;
: ?; i4 L! {7 n+ l- _! c* G: U              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 L# t8 K8 ^2 z2 N                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# N0 B' }7 r6 f) M1 `                        }
# }& F& N3 g8 w+ _6 `- I$ Z+ n                        else//输出暂时还没有改变数组元素的值7 ~4 s: w/ p/ z6 y% U1 R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) y- o2 D( e4 u: a7 h, B5 C+ |" k                    }
8 u# P( n% m( g/ Z9 A7 W9 p8 b                    else( w) _- m! z+ h# D, F
                        i++;//数组元素为0,直接跳过,不计数。。。" R# M3 Q+ o  c1 H3 c0 G8 o( ~/ w) H
                }6 x" C& J# M! _
8 }" L' c1 t! X7 P* }
' c/ G; N5 @  e7 a8 I% |+ k& P' ~
            }//结束while循环3 M9 }( \5 H8 [! y: [: D2 ]6 C
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦$ J: g% v% ]6 K0 Q6 q
           6 C+ B' _9 }8 K" B# h
                if (numw[i] != 0)& c' C  G# S' v; r; {5 i
                    Console.WriteLine(numw[i]);
* a" ?, z6 F  [5 O2 W( W+ Q# F) L           
% o4 R3 x0 V# A+ q            Console.ReadLine();5 H( L/ F" H! S9 e! e
        }8 b7 V# ]1 v5 x/ Y* p; q5 C
    }" V" k. L2 G1 h- [  z9 A
}5 R& w7 k- A* _4 r
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:23 | 显示全部楼层
循环队列。循环链表。。。
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-12-28 07:02:46 | 显示全部楼层
这个题目就是经典的约瑟夫环
小甲鱼最新课程 -> https://ilovefishc.com

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2026-1-19 04:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表