鱼C论坛

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

猴子问题

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

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

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

x
大家好!7 Q  k: ~3 e1 ^& E" r+ |; z
这几天我在忙着编一个问题,我用了一种方法编出来!
/ N; ?. _" |' A" t1 I: w0 n但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
' @: P4 N% ?# f; g" a注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
. z/ |$ t( h. k" s4 }/ F( Q" W
! L8 ~3 l7 y; y( K% q# y8 B$ B+ S5 r
$ y5 m5 n" o4 G# Y
                            题目5 V$ V. I! n, M+ K% M2 _
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。# ]9 R7 o9 \8 ]! ?( i3 a
第一种方法:利用循环链表
( V7 t( n& w) M% Q#include<stdio.h>
! I; x- M: U7 G- h" x7 O#include<malloc.h>
1 z+ P2 ?2 X# [0 t/ j: Z#define M 8            //共有8只猴子
4 q$ W5 Z- Q; C$ N5 J; r7 \" w#define N 3            //数到3只时退出第三只
1 ^0 _0 {6 `% k' \. v4 Btypedef struct monkey
( C# c/ c" y& a! n$ w{int number;2 v7 w$ V5 X+ ^6 n9 }: V
int flag;3 c" g- H8 J; m3 J- \
struct monkey* next;  A+ I+ p  @. P# M2 S: s6 @
}MONKEY;
" s  U. P7 @, j* _! Bmain()
/ z+ D4 a* i7 P- }6 k' t{ MONKEY *head=NULL,*p,*s;5 |1 P: g) I( p8 r3 y
  int i,sum=0,count=0;
# L0 l* L0 q  W; c4 j2 ?  clrscr();              //清屏  u* e' b$ K# C2 a
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 g: L7 m- J" l8 |8 X) D) E  p->number=1;p->flag=1;" {/ F$ Q- w) u& N2 F0 N. U
  p->next=head;
0 D+ }0 r1 p: z/ f% C  head=p;
9 T( F  u% J  i( P# y: y) m  for(i=2;i<=M;i++)' [0 `" ]) A( Y
    { s=(MONKEY *)malloc(sizeof(MONKEY));' m7 Z" S, T( M3 Q7 ^
     s->number=i;s->flag=1;# R2 ^% v# X8 S* x+ q1 N2 D0 j
     s->next=head;
7 E, K7 O1 Y+ P: |! r* }     p->next=s;p=p->next;7 s* ]6 s! \" @3 ]: t  d! O
    }# ^! x$ T# a8 M' T; b4 J+ ]$ e( V
    p=head;2 H0 Q! p' T7 }5 t* q
   for(;;)
6 |$ w6 P) e; \; K7 s# I8 D    {if(p->flag==1)
! b/ A0 k0 }0 x: ^2 }( b. l       count++;
, v$ l, r$ v( t. c8 I9 O- \4 d( K     if(count==N)
" V  s2 D5 _. v8 s% ^4 q        {p->flag=0;4 m3 ]& N  @. |3 S. v
         count=0;
1 i0 t+ q+ M- R! u         sum++;}* ~6 P( N$ z, i% R
     if(sum==M-1)
! I! I  R+ k% S- D5 V( [9 i7 S+ r1 t        break;  a* o' b! O- `  M& S  i( D
     p=p->next;
' n2 c9 K9 k8 x) ~    }. O1 t9 ~- b6 c% i3 w+ G' U
    p=
* ^9 S6 w% X) W( h7 h$ B    head;
$ X1 K6 j6 }& r4 A- g# R    for(i=1;i<=M;i++)4 d8 s6 b2 q6 V! a4 c; y) B
    { if(p->flag==1)
/ O- [# X4 ?9 x        printf("\t%d",p->number);, Q4 ^$ L$ Y) ]7 p, F2 I; z0 [
      p=p->next;7 I4 s( W  z, s$ ]& f1 f
    }
  y. o7 e0 n0 s( `/ O% W
$ Y7 m. d2 f# q5 p+ J& y' `* {/ e: P" M( ?
- \4 N1 X4 s) J0 \' M% b
}
" t) f* ?" c% t+ l) Y
第二种方法:数组% ]) t" s  O6 `. p! r, T+ Q
#include<stdio.h>
" ]( l1 F. u% {% u& y#define M 8
; V6 x" c( n3 b$ ?" Bstruct monkey- A4 y' y/ W7 ]1 b: \8 w- G( K
{int number;
! w: X  @) F! m- h! M; cint nextp;. ]. C, G& K) j
}link[M+1];
/ A- r3 j/ t) Q% X* h; w- K0 Y+ u6 O' ?1 P7 V* S" I8 Q& _" F1 |
void main()7 L8 ^/ Y: T$ @4 G
{int i,count,h;
+ ~4 `( E- S+ n5 n; P6 R3 |  Jfor(i=1;i<=M;i++)8 c3 G) A& s+ [- P; l
{  if(i==M)
! J* {, a1 P4 b& K4 A7 A  E5 |   link[i].nextp=1;- c3 U2 s( C6 A2 n3 O8 K
   else* R2 y0 f# C* W( ?( R
   link[i].nextp=i+1;, Z' ^1 |+ `- M# V4 c+ n
  link[i].number=i;  D7 n6 f' ^7 s" u
}0 g  ^! H$ W0 D1 K! j
printf("\n");4 G5 F$ u' C) k8 T7 L9 }
count=0;9 C2 S. T1 a) H* z$ v/ T: Y  y
h=M;
3 h9 q* C% i5 H7 j, Q5 Z( o' g$ eprintf("依次退出的猴子: \n");
, G. `. |2 d1 ?/ qwhile(count<M-1)
- H+ Q3 _9 c( {+ j. B2 R{i=0;8 W" P8 Z  g; J( P) ^
while(i!=3)
4 o0 U; B2 F/ Y+ g{ h=link[h].nextp;  k7 c$ }: |. Q4 M  t
   if(link[h].number)
+ V0 s9 }( X! d* a$ p9 i" b% H     i++;}
/ V4 @; V' Y5 ]0 k$ }
( h) P, D( S4 `5 a2 cprintf("%4d",link[h].number);
$ f0 j2 G1 z( l5 A5 U2 plink[h].number=0;4 p# p  D# Y/ e, C$ q
count++;
; n, \9 r& x; V) Z7 j$ e}
) [& }/ p3 S# d1 A9 g4 y
7 o* M/ o! P5 i# S4 y5 I, T5 ?- [printf("\n大王是:");) ?* E! j% ^1 D1 V: N3 \
  for(i=1;i<=M;i++): h8 t0 j1 {) e$ v
  if(link[i].number), S$ `0 w; R6 d1 }% C
    printf("%3d\n",link[i].number);% z2 z, }3 P$ T' u1 b- f; V1 o$ v
- V7 z3 u  T1 I9 s4 Y  O, r9 @

, J  I' V7 [; \7 T. T) _* i}
/ I4 Y, w9 q- P& o
第三种是普通方法for循环

# r4 l% O: P  q- H9 q#include<stdio.h>* n6 c! I/ P2 V) W
void main()& }5 |2 f$ o( v- f2 D
{ int i,k,m,n,num[50],q,*p;
2 n% c3 i0 o8 Q  m    clrscr();
+ |$ E( S8 l# B* f& y* T   printf("input number of person: n=");, k* B3 d+ O$ A* Y& o
    scanf("%d",&n);  n: e" `4 g% P0 g5 |
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只, g4 p( @! w& V. C4 s
    scanf("%d",&q);( @3 y/ A# p6 h; ?# I
   p=num;
6 |! S( Z% G9 ^' `  for(i=0;i<n;i++)
9 V, ?2 Q! V/ T1 G' N" `/ z    *(p+i)=i+1;" N8 |7 p4 O, G% z- [# k
   i=0;. P% }/ w8 T  E# x. d9 g
   k=0;
& @8 I6 ^" D6 {   m=0;
" q- F% H+ ?9 h' T6 |% |  while(m<n-1)
0 p/ j0 e% c. A: T3 E% e/ G   {if(*(p+i)!=0) k++;
4 {# }$ r& J' r! C% C# S     if(k==q)
! G2 }# T# x3 s% N9 U4 v      { *(p+i)=0;
: L* [# g0 W# h3 `# ~        k=0;( e2 ~1 P7 d3 l* ]1 S- |0 O) Z
        m++;. P6 x5 F! D. P
      }4 B# k! G' J( ]  s
    i++;
# U) ]# Z+ [9 {, M4 ^5 q8 z    if(i==n)i=0;
1 @7 a* m1 `* W7 T   }, `+ V0 F7 t9 |
  while(*p==0)p++;
. l1 w  Q7 s9 ?) P, i    printf("The last one is NO:%d\n",*p);
) Q  V8 N! N. G* Q) j     getch();
- g& p1 R) w( W8 ?5 K# Z- V2 v. t+ L% i% D/ ?' @4 u
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; C5 n9 ^, S; O) W( m  b2 Anamespace 又费马达又费电: n  W+ z: X' G+ Q# e7 [% ^
{" x3 n2 I4 D* B* q/ j
    class Program1 N, M* |! |% g8 ^, @) Z4 ?
    {
3 E# o% c) n5 q" @5 m) Q        static void Main(string[] args)5 E3 X+ H7 [9 V7 i7 x' x
        {
: w- H) T2 K1 [5 `9 Q; Z            int m, n;
6 j# }1 G! h% o6 q( Q& P  W9 @            Console.WriteLine("请输入数组长度");" Z  j* U! k1 n3 ^) T
            m = int.Parse(Console.ReadLine());//m为数组的大小6 |9 x+ U. n% d& ?6 k/ y
            Console.WriteLine("请输入要截取数字的大小");
9 n1 z0 D3 p+ h* G. _" t            n = int.Parse(Console.ReadLine());
* E7 E$ k$ r! ?* i            int [] numw=new int
" y+ G3 {% k# c  \/ X
6 _. V% Y5 j2 @2 p&shy;&shy;&shy;;! o6 X5 h& q- N' n# C% u. B
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
3 o( [7 E! W' @! k7 h; T            {
4 S) Y  L: f  E& X3 J( n                numw[j - 1] = j;
* X7 @+ j4 z5 p$ a5 j$ H            }2 e! {1 Z0 s8 B1 |9 G# V# a
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!4 V7 k$ R9 y- X; `
            while (d != m - 1)
: X* M" k, C+ d            {2 f. i4 o( R6 E3 C" O' j% c' i- ~
                if (i == m && d != m - 1)3 I+ X) T  ~% v7 U# n
                {- m! R8 q1 w! P. w9 `
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
; }9 f6 S; [+ Y* g$ j                    continue;. E& V" V6 w: }6 V, b# d
                }) A: R0 T8 O$ a8 O
                else) t0 R( `/ {1 b# i2 M4 A9 F
                {' M. L9 J1 ?3 t5 T& }' K- m
                    if (numw[i] != 0)% W, P4 f7 h# b: g" L# m- S
                    {
$ e3 m) A5 ~7 T" k# W, z7 b8 V                        i++;
, E3 o9 V% k# J' p7 |                        k++;6 c: n& I. \. H3 ~1 k
                        if (k == n)
& N  c- e) n: Z+ `. t$ u                        {
6 G" P2 S% t( Q0 s. x                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- I+ q2 ^( j: W0 p" ^+ i; z                            k = 0;
3 `8 @+ W$ i1 q: s  S              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# P5 S# S+ C5 [$ r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 d/ E& R6 h. I! s8 r                        }
* J) D  E0 Q2 @! t" \7 H                        else//输出暂时还没有改变数组元素的值
4 M2 ?2 @) e- ^  o' x$ A7 l                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);$ T* l8 U. D8 Q( s* t7 V; y
                    }
  U4 R1 S. K5 t& J3 l                    else
: {1 e; `, p% H( C: s4 S; T                        i++;//数组元素为0,直接跳过,不计数。。。9 X8 E3 W0 T0 E
                }/ @. o9 U1 A7 M

+ w: w( I1 T" M+ E9 D: {( L+ P/ E, Y2 [2 p
            }//结束while循环
' Y* K- K9 ~3 g! E  l8 o- I7 K' G. M            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
: }1 I% i9 m( f) t           
- {% N0 ~  ~4 C4 u0 K                if (numw[i] != 0)
% B, P4 F! t4 |& d                    Console.WriteLine(numw[i]);
8 o8 t$ @3 ?4 P$ i) ]0 w6 Y+ u           8 [& r0 O0 E9 u
            Console.ReadLine();
" |, c/ I% Z; \5 |/ Z0 Z        }
; O8 ]# i. u- |) g# L1 h4 q' d- p    }
  E$ A4 @5 i8 R5 C0 p5 I}1 r0 P1 u+ h! g- o# u" n
小甲鱼最新课程 -> 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-2-13 14:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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