鱼C论坛

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

猴子问题

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

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

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

x
大家好!
. Z! J* [- O! c4 _这几天我在忙着编一个问题,我用了一种方法编出来!
& Y# _9 O; z- Z9 q" P' K' @5 W; f但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
- y. l) _$ ~0 d# l" x! [注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
. `+ _9 r3 n1 O2 v7 ^
+ J( k" G! O) Y# M" i. g/ y7 M% l; s# M1 K5 n
                            题目! i; B- G! E6 A. K
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; M" p( z, x- m  @% `: C第一种方法:利用循环链表( x6 Q! P) @3 d/ D0 Q# l
#include<stdio.h>& @, {  \6 m# x
#include<malloc.h>( S/ w# {, v+ u. Z1 n* h
#define M 8            //共有8只猴子
: r0 A; r; t5 E" Z4 U% n#define N 3            //数到3只时退出第三只
) c% [/ d+ ]0 y" m6 L' K( p# y5 Ztypedef struct monkey
0 B* W: L# o% N2 c/ }{int number;  o. E- F* @4 J4 u" o
int flag;/ t7 P$ S2 U% y
struct monkey* next;
. z* o  d! A- T5 Q" s}MONKEY;
4 T7 S( W' J. C' Z0 A$ Cmain()% g( ]' ~6 X  I
{ MONKEY *head=NULL,*p,*s;5 D% t: q$ N4 q7 {1 d7 W+ Y
  int i,sum=0,count=0;
( O: f# p" q2 U; H# g* X! Y% [9 Q  clrscr();              //清屏
' ^  P4 E5 }* Z; u7 b: F+ h/ `  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存$ u% v) S9 _2 b& Y* C8 M
  p->number=1;p->flag=1;# V; P& ~$ Q3 B
  p->next=head;2 G/ F3 j) k4 `  d) N* E; E0 L
  head=p;
8 E' c+ N* b* n& s  e/ Z$ l  for(i=2;i<=M;i++)
. F- ^3 R' @- F    { s=(MONKEY *)malloc(sizeof(MONKEY));
5 r& n3 L2 C8 H$ l, ~     s->number=i;s->flag=1;
: L3 h1 H+ S3 ~+ N- h     s->next=head;
2 [' a* v6 G- h+ p+ r     p->next=s;p=p->next;
" @9 T, y2 w7 \9 y" ?% @    }
; q% ^1 [$ H/ Z; A, F    p=head;
" U/ n5 L' b7 O5 e' Z   for(;;): f: j1 T: ~6 h/ ]. N7 x8 H
    {if(p->flag==1)  {$ R% B8 @; B1 x0 z, l7 X' _
       count++;
5 Z" J1 u: }- `     if(count==N)
3 B4 d0 h9 @2 E6 Z2 E( ?. X3 h        {p->flag=0;
* U- Z- i% D% y7 @; c         count=0;' ?2 j/ s: q. t5 \4 R; v
         sum++;}
  l, m4 P7 N+ |, s" T* y$ S2 y6 }     if(sum==M-1)
; m: T2 ^1 a9 ?$ D4 q        break;" k) Q8 y- o3 I
     p=p->next;, H+ F- r, s2 g  t0 {: h/ a! _9 i% C
    }& N" O# Z* Q) d  O5 F
    p=
" W1 a; S! s' E; A9 e9 {* D! ]    head;
! I# ?, u6 h* T* k* [# X9 X    for(i=1;i<=M;i++)
! T- i& j6 W" P" d; C. c    { if(p->flag==1)
5 Z3 I: m% |; P) {; R        printf("\t%d",p->number);& z+ e/ H; K9 v$ Q0 ^* L6 b
      p=p->next;6 U" g" c4 G7 ]7 s- s5 I  Z( t- q
    }& X" h# Y& |) U0 R

1 z5 m2 C* w0 r1 L# E, e' x. M/ \% O: H+ L. N+ x

5 \6 o* a) S% i3 r}

  R, O6 D, M! M第二种方法:数组; q: V; [$ i$ w$ p( W/ X6 Y6 ^
#include<stdio.h>0 w( p! x- g: K' O( Y
#define M 8
, }- C8 r2 G$ g' V& {struct monkey
8 N5 `3 Y% o$ Y& [. {{int number;7 ]8 A( l, {1 a2 i/ D9 P$ ?
int nextp;) k* Z  J$ H) \) ~, z
}link[M+1];2 w$ b/ M; o* @8 E$ p0 A

7 `( j9 [0 k9 @! A2 Xvoid main()
1 d- c+ N& e; R+ ~9 n/ h{int i,count,h;% c& _6 j2 f. l
for(i=1;i<=M;i++)9 |# g3 T5 ?1 B3 a0 ]; a3 r
{  if(i==M)
. `# g  `1 c: l% ]$ Y   link[i].nextp=1;
0 S8 F$ V7 `$ }3 t   else
+ S& l5 x; p7 u6 O3 `0 {   link[i].nextp=i+1;1 Z) m& e$ J( y1 X% m
  link[i].number=i;
5 I" l4 R# c. d0 F}
: p& k/ o2 Z5 x8 yprintf("\n");5 p. e7 q$ [$ D/ O2 W$ t0 E
count=0;/ Z, Q5 K- u# S6 o3 a
h=M;0 E! t7 h9 Y: t# ~# f# o: {
printf("依次退出的猴子: \n");5 _( M4 t. X4 S: ]/ i; E
while(count<M-1)
# [/ [# E. v6 a2 w% O+ B0 |! N{i=0;+ I. I" M9 c8 X- P! v2 c
while(i!=3)* |8 I! [$ {: N/ c! s# c. b, D
{ h=link[h].nextp;5 R3 K/ J' B$ o, Y8 Q
   if(link[h].number)
' z  u8 k+ w- y0 G* g5 i# h3 l! I     i++;}. Y2 E. U1 S! b2 D6 q! r6 g* E

9 T$ T; V; k; f  Dprintf("%4d",link[h].number);( U3 {7 c" C8 q! a, G
link[h].number=0;
" E- D- H# a& J/ R4 Scount++;
" q. `7 U: M+ O0 O9 ~. N7 [! Z% o}& Y6 I( J  i: W+ v- d, n, P
% v1 N) C2 h! v' h5 u
printf("\n大王是:");
6 v9 h# l+ f. N: O$ O  for(i=1;i<=M;i++)
. B7 B! C& A0 }+ q9 H' i: q  if(link[i].number)
; v. c4 N) B# m* f) I' A    printf("%3d\n",link[i].number);
- P- m* V) e7 G/ m# n. O* y( l0 F: |1 A4 \* [6 u

6 g- e9 D3 V8 ^}

6 |* m% V+ w) w& P1 O第三种是普通方法for循环

# O. V) {. `2 l/ h9 {1 k5 S#include<stdio.h>
1 v( ?- s2 I, k( N6 m! xvoid main(); \% y, t) V( P5 g( F9 F
{ int i,k,m,n,num[50],q,*p;9 c4 ]$ v6 X+ ?2 `: V
    clrscr();
- t) Y4 T# f0 Y6 u- B# ^; [   printf("input number of person: n=");
" {$ S! s8 u8 }2 x( I( ?( Q* J. R7 ?8 d    scanf("%d",&n);
3 ?9 D5 j' m6 I7 C# sprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只0 n6 Q2 V) h8 J4 Q
    scanf("%d",&q);5 X& q  V+ ?, f5 m1 g: y( R8 V
   p=num;) j: D" J0 i/ b+ \: W. O8 I
  for(i=0;i<n;i++)* C8 m3 [4 ~% v- u0 N6 ]& c
    *(p+i)=i+1;
1 b8 O0 l  g/ Q  `7 G9 U   i=0;
1 O( M) }7 |5 ?3 a+ H# d   k=0;
" m3 e. N# J* \+ L" z, c9 D   m=0;
( u* V! Y: k) Z' \, ^  while(m<n-1)
4 S4 ^- ~) Q; Z& B; o5 e   {if(*(p+i)!=0) k++;
( p' `: v4 X( D) P" l1 F/ X- i     if(k==q)
7 |. \1 M) v+ n& n- y      { *(p+i)=0;
4 i2 m5 i  s& R- S        k=0;
' t0 |7 @7 J7 s2 Q        m++;
, v2 Y8 M2 W/ S      }
% ?. z4 ]( z7 c0 l: R' A8 D    i++;) q  Q7 g! W7 H3 ]% ^* {0 p
    if(i==n)i=0;
% J% o# Y/ Y" G* S; p5 |& ]. `8 T: h. w  `   }- w9 o4 e& ~2 {8 t
  while(*p==0)p++;8 Z$ z2 }, j% O6 O( a
    printf("The last one is NO:%d\n",*p);
1 E  C+ i' |6 M* o% W* J     getch();
, C# k4 n1 C3 u+ M5 E: g1 }1 m6 ?- P+ q* Z) ]( ~/ d0 E
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;# w) m4 l  O5 M3 X% |- a
namespace 又费马达又费电
4 j' }# q6 ?) k) S9 `6 N{9 I% H# W5 S4 s% L# S
    class Program3 h  m9 J/ x* _. t# M' U/ H& s+ v5 G
    {
8 V2 Z: B" i2 U* K        static void Main(string[] args)
) B3 A+ P( F, ~, V4 K  D5 I( |( s        {
" \/ i- o% C* A5 u) s4 s: X            int m, n;, D- K' h' ?4 \, T3 ?  x0 Z
            Console.WriteLine("请输入数组长度");
6 B1 w/ \. h6 C- S& f3 t" \            m = int.Parse(Console.ReadLine());//m为数组的大小
8 e" }' M6 ^' U* W8 n( B4 x            Console.WriteLine("请输入要截取数字的大小");
+ F  D7 B. Q  F+ i            n = int.Parse(Console.ReadLine());8 O' Q- j6 Q( @  p1 o
            int [] numw=new int
' K" ?% I( C& ]
+ |9 N5 A! e! e9 w&shy;&shy;&shy;;
- y+ d6 X6 E0 R$ ?& N; Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数( k: K- q" }  f5 E0 J& p; Q; U
            {4 a! J% I# X3 e2 Z, _
                numw[j - 1] = j;
0 d! X- [3 }0 {9 C7 m4 s            }) i3 l9 ~5 S' Z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!  H& T) n1 z% `0 K- h2 n- F' o
            while (d != m - 1)
7 m6 e# F' ]8 E, K1 U            {
5 t4 l9 F/ l1 F  U1 i9 T                if (i == m && d != m - 1)
. p" H1 M8 W6 @' f" C4 R  a                {% R* F+ ^; F+ u5 v3 i
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
! z0 ]4 q6 Z9 [% C                    continue;% Q6 b, u3 x- e% k4 r' R8 u0 ?) e2 }
                }
2 T8 q7 |8 @. d, d8 B                else' C& L$ b! T6 i4 ]
                {
) }6 r, |4 a% R% m" _0 ?                    if (numw[i] != 0)# w: F5 Z* \; l% s( S4 F
                    {
6 z+ n! b# s. d1 |& _8 e                        i++;: N" x3 K" \+ |8 Z4 p. \+ e+ M2 ?% I
                        k++;
( Z+ \6 e! D1 j% o* {6 Y  `                        if (k == n)2 r  k& A" c2 q8 P8 ~
                        {
( I, M3 i8 F  O4 E3 a                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" `7 D* @# h5 G0 }/ j# Z* i
                            k = 0;
  x/ ?2 D9 d+ \0 Y' {              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1+ R: K: A8 ^& O: ^  C# {5 _
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
+ D0 A3 `4 @7 @                        }
6 @8 E# f9 w# o  {$ T                        else//输出暂时还没有改变数组元素的值5 X+ f5 n- N$ T: b% X: ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);" v+ z4 W8 j  D% p, U
                    }
; W/ N) l3 \3 K2 Q* K/ S                    else5 A2 L8 g7 O: ]2 C0 R( p4 K0 o
                        i++;//数组元素为0,直接跳过,不计数。。。* `7 D& T% R& }+ v& V; O% N
                }/ w( N+ ~* i6 K  U) r8 K7 J7 [
2 {  d2 V' l8 ^6 d

( j7 {) E& Z2 k$ M' I2 ^5 t  h            }//结束while循环5 b$ k! v& G9 ?) \" }+ _- u( a
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦0 F9 {: R. |, |% f* W# A3 O
           . L7 {/ i; l/ w
                if (numw[i] != 0)
; ^8 o0 [% H2 }( L1 m, S* s) j6 R) E. _( V                    Console.WriteLine(numw[i]);
% _1 t( c- x# k' B1 T5 B+ @' D           
9 i2 z/ u  L& e' `            Console.ReadLine();
& U$ z8 i6 }/ y* b9 B  i( @; c        }
0 U2 F  ~# }: t8 w, _    }% M( a9 F0 h9 {7 ~2 `* y5 `+ q& [& o
}
, f2 V/ U* t% d- F, E4 p7 ]9 Q
小甲鱼最新课程 -> 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-6-29 07:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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