鱼C论坛

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

猴子问题

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

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

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

x
大家好!
" N2 _% L  t5 a+ A) x& `这几天我在忙着编一个问题,我用了一种方法编出来!
2 ]$ n( ?. C! v% w但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ B& `+ r3 B% V
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
, P; s, o4 N9 ]' X  P5 t* [8 s5 h. z6 C! l6 R9 l/ p1 [7 O4 }: a
$ T* `/ X+ o& p
                            题目
" o, R" Q; Z* t3 P山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
2 a& f" `1 s8 K# x第一种方法:利用循环链表
5 `9 F# E5 A: Y& g$ H& u#include<stdio.h>  s+ P+ E  r, _
#include<malloc.h>
, J# D8 u. u6 ]1 @, e0 O1 T#define M 8            //共有8只猴子
8 H. D) \  S1 t2 M/ l8 T#define N 3            //数到3只时退出第三只
# ?0 d- O; N; F$ o# [+ {$ Rtypedef struct monkey, f& w' W( H4 i4 u2 _
{int number;
3 _; C* ]! `" B. x! H, |$ eint flag;
1 F& C7 _: a% K$ u( h0 x* Ostruct monkey* next;: v! i" ^7 j  I0 r' m* g
}MONKEY;' t: I  l# d( }; @! w1 y
main()
; m; D  x+ l, ^% p6 h{ MONKEY *head=NULL,*p,*s;
9 s; l! P- @! ~8 ]8 Z: Z3 z  int i,sum=0,count=0;
2 A3 d) j- g7 B' _  clrscr();              //清屏
$ z# O  h5 n% j0 g+ z* O  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  L/ o5 }. _, v$ q3 \- P  p->number=1;p->flag=1;5 O' W$ I; @7 h
  p->next=head;% g8 w" O4 I: t! z5 B- C% Q
  head=p;
" q6 ~& l! T+ N5 Q% k' z/ x  for(i=2;i<=M;i++)
) K) ?3 Y4 K: D0 B, T6 B- N5 k    { s=(MONKEY *)malloc(sizeof(MONKEY));
8 F# z* ?4 v: q! W1 O     s->number=i;s->flag=1;
0 D. O3 `% _. I# v& z- {3 J, T, T! j     s->next=head;7 b$ |( [( t/ }, E0 L
     p->next=s;p=p->next;) j9 t3 L5 H' V
    }
0 W: d) I8 H. I( t0 q    p=head;, X4 Z' T+ ~" d: I9 s  R2 L$ Q
   for(;;)
+ e2 M* t6 K% W' _! \1 |1 @) O3 E' u    {if(p->flag==1)
5 z/ t$ S: t) Q9 h1 ]       count++;
2 b# \; `. Z2 i, i     if(count==N)" k9 y1 s/ l: v) }  O
        {p->flag=0;
4 {: ~$ u& ~+ U9 |: k- {         count=0;
1 a9 g) h3 d2 L/ L9 f         sum++;}+ S/ i5 B4 g$ @' T9 i& I8 _/ h: ^
     if(sum==M-1)5 k4 V3 Z: j3 b9 p  D5 Q( H
        break;+ H- N7 n1 ^4 M' g* r
     p=p->next;& y5 o5 B, t2 A' R
    }
' b8 D, ?5 t  g3 E2 f- ]9 K, ^+ @    p=; u) b% K/ }0 J/ u1 @) r2 J3 x+ V4 L
    head;, I+ b5 G6 x4 I- j3 ?* }9 V
    for(i=1;i<=M;i++)9 h8 z/ A. y/ c5 ?9 y
    { if(p->flag==1)/ ^$ z& L6 @' T9 Q' t- E
        printf("\t%d",p->number);
$ j. k9 w2 y) O      p=p->next;
# Z0 d4 m& m. I1 I    }
% i9 C1 S3 V2 O- T6 B! K2 [. I' Q  w6 x" v
9 }+ W3 M" X, L' ]$ A9 c

4 a6 x7 X" y3 M% [( D6 \}

. T& T. K/ b+ {# g, i, j第二种方法:数组/ v* `0 t9 _3 X! I9 I( C
#include<stdio.h>
* H* {2 w( R/ A3 B* g#define M 8
' U6 i( l/ j, K6 h3 M! fstruct monkey
: G# o2 b% D* G8 W2 i% h- [! r3 I{int number;7 o" Q2 c5 J# l& {+ t
int nextp;
) \9 }& E8 S+ x) E' H}link[M+1];
9 N9 H# b( Q' o/ x4 H( d# c  u0 g( X
0 f0 L4 q; E7 g! n9 @void main()
' `, v% l  U  x0 ?{int i,count,h;1 \, p5 p4 a- K
for(i=1;i<=M;i++)( t' ~! p. Y2 Q! r
{  if(i==M)
' c- A% I. D1 r4 V   link[i].nextp=1;
' E: L" [2 k. n6 _   else+ V# ?) i# Y  i/ A+ t
   link[i].nextp=i+1;
' _2 l2 A) C6 f3 H( B5 m5 J- y. s  link[i].number=i;
% F* Z: S3 K1 A8 f6 V& r7 @5 @4 p}
1 @6 z+ {! z4 K; s$ hprintf("\n");
$ _; V2 _1 A3 Z4 q( acount=0;- A4 y% n8 i$ i8 z& a
h=M;
2 A+ t% j, b4 [printf("依次退出的猴子: \n");
! m8 e7 h/ m9 @. A, ]while(count<M-1)
! k' J1 P9 _  q4 b; d4 P{i=0;# k8 I& ]) ?7 A$ C
while(i!=3)
1 j8 i5 b/ ]& V( N2 f, k+ ^{ h=link[h].nextp;9 Z* ~, _& R, a" q; H. O
   if(link[h].number)& |8 a3 e, ?0 u$ r+ Y1 M: ?8 R4 T7 [+ J
     i++;}
$ I8 G. A) |  b2 t) O6 f
9 \5 k7 F6 P9 N0 kprintf("%4d",link[h].number);
; x. k* \2 y2 Q/ N+ ?# e0 Qlink[h].number=0;
8 P+ v: @+ N. u* icount++;
9 p8 h. r3 B) N6 D; ^7 x9 J}
, C5 Y2 u/ n, S* j# i1 U6 \- H
. u1 d' k/ n# W, qprintf("\n大王是:");, G4 o5 h+ ]: B: S8 d4 a
  for(i=1;i<=M;i++)
5 i: L7 L9 `2 {  if(link[i].number)
6 i1 X/ I, Z) h/ p# q. V5 @( ]    printf("%3d\n",link[i].number);4 Z# ]2 G3 M9 @6 u8 i1 W
# o) U% X+ m0 ~

$ A: E  p. B; \" b9 h}

" ]5 s6 Y+ o5 N( I* w第三种是普通方法for循环

, N: l1 h' ?6 j6 U' G; T) Y#include<stdio.h>0 J) v; e5 d/ J9 E' H
void main()
0 O% o$ N% Z8 s. S# K% y{ int i,k,m,n,num[50],q,*p;* e  t% v2 u2 a
    clrscr();5 B6 Q+ _/ v+ z# i
   printf("input number of person: n=");, {% I1 o7 @4 J1 A1 f5 u' a4 N
    scanf("%d",&n);
! W5 W5 U5 q0 b" Eprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只, }, q  Z' d5 t: R/ O3 J
    scanf("%d",&q);: X  u+ d& X* ?, c
   p=num;
! N4 i& t% h# j) A- S: s  for(i=0;i<n;i++)8 h- y5 H6 v+ P3 C( S) m5 }5 o
    *(p+i)=i+1;
4 r2 |2 B# u- }! R/ i! ~+ W( i! K   i=0;( F( N1 D  a9 g
   k=0;
. W1 y3 `4 u, W! B# U1 A( d   m=0;
) h2 Z; o1 p- K4 q  while(m<n-1)% D9 b" x5 z' p4 I
   {if(*(p+i)!=0) k++;
2 i. B% |/ n. @) d: K     if(k==q)
& w4 \0 F$ n+ S+ Y9 |3 k      { *(p+i)=0;
- @2 B% y( O0 ?6 B6 n        k=0;. n7 q3 E. H$ i" Z7 h
        m++;
! t' I! r  Z0 D/ b- H      }# D" a! x8 |6 v! S1 O
    i++;
: Y2 g0 K* u4 p' {  ?) ]    if(i==n)i=0;# Z) @8 [1 ?3 h
   }5 i0 t' V! a- L8 w  O  ~  u* O
  while(*p==0)p++;
+ b. v; S& i: B6 v( j% ^; i    printf("The last one is NO:%d\n",*p);3 A# g7 n% l* ?( M/ V( ?% F3 H9 @
     getch();$ h% H' x1 m4 G; n5 l

: M. a7 r  B" g8 v+ M; T8 C( J8 W) U}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
! O& z; z5 [4 g0 D/ B. z/ ]; Vnamespace 又费马达又费电
$ ~7 e- O2 K& P  c) j{
" y6 O9 _7 ^4 g. W1 T3 Y- D    class Program
+ Z# ~: s- g9 p* X3 w3 ?    {
- O4 \) g# V' }        static void Main(string[] args)
0 ?  n, d$ n; g, m$ g8 _        {
1 Z5 k) F$ R% Z7 h+ Z. E; U  D            int m, n;
, N6 _2 p7 H9 e8 [            Console.WriteLine("请输入数组长度");
; X8 h  a& o, W% O$ p' h  R; @7 {% E8 U            m = int.Parse(Console.ReadLine());//m为数组的大小  @) q4 c" V8 z
            Console.WriteLine("请输入要截取数字的大小");; ?/ I9 f" \, T1 W7 q0 z
            n = int.Parse(Console.ReadLine());, L5 p* Q. T, p) u
            int [] numw=new int, O3 C; H  p8 H0 K: m# E! N- V  T

' d1 R3 V7 y: I# T2 x% L) }&shy;&shy;&shy;;
  v0 K; ]9 s. Z            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 w% R4 [# t: p" J/ r
            {
4 Y% S$ ~  f/ `& w# o9 N                numw[j - 1] = j;
) U, t* |$ e$ W7 ~            }" x2 V1 ~  F# _9 n) R  g) v
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
: @7 O2 Y; n" `% c( X9 D$ c            while (d != m - 1)( o& E6 A0 j$ T
            {
* L" Q, y  i. M$ |                if (i == m && d != m - 1)
( `$ o7 v, j" a. W' m  J3 S8 e                {& h$ [9 Y0 w; X  B/ t5 z3 [
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!, W2 o' V/ s) R. e
                    continue;
- @& u. `# q" j2 k                }
/ H, G3 Q9 D* P0 J6 V$ K' g2 u' X                else8 `8 L2 Z% s6 E$ V9 \' M7 P
                {+ }: w& ^! |" y
                    if (numw[i] != 0)
0 L% r* J# D( v: v                    {
- I# j* P& L1 K1 f3 S9 y                        i++;0 S0 L/ P  p2 B, z. i( `, g
                        k++;: M7 c& K0 R; e( S' K
                        if (k == n)
: X% L# E9 x$ Z8 z# ~                        {6 A" s2 H9 C% v& Y/ ~
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
4 _0 I4 u* B; I0 D& s' i                            k = 0;
9 n- Y1 ]  Y% |+ O; T, Z              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
! q6 O* {5 b8 I: G- W0 b                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' U, p7 R0 W/ W1 t' u' M5 ]                        }' y; m* E' X# {; x
                        else//输出暂时还没有改变数组元素的值) G  q3 O6 a8 V! `
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ P1 S/ u+ ^: x' U- v                    }
7 O2 n" J- l. }6 e4 s, N                    else
6 Y1 {) y  s7 F1 M( {$ L                        i++;//数组元素为0,直接跳过,不计数。。。
0 ]3 T6 v/ ?+ l9 q. c9 ^8 U                }9 O! ]$ P9 `' o

- _' P6 k& @/ B+ g0 @) t
: H4 d( }+ H9 v. |  P! e+ `" s9 h            }//结束while循环0 L8 {3 u5 M) q( [7 V7 z
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ G9 o! K0 V2 v7 U6 J" W           ' C0 L* o: ~; ?
                if (numw[i] != 0)% b" p* n/ k3 c$ H9 ]
                    Console.WriteLine(numw[i]);/ F; r: n% e  N  ~- g6 W
           ' P+ V' }6 {  O! j8 x
            Console.ReadLine();& G+ l/ x$ R) _8 f
        }
: ~: r; ]/ Y0 o" L% ^% G1 q    }- p3 ~2 @9 P& F4 ~: \- L
}
  g$ e* h6 L& e
小甲鱼最新课程 -> 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-20 01:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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