鱼C论坛

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

猴子问题

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

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

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

x
大家好!% Z) _4 F3 Z/ N$ a# X+ S
这几天我在忙着编一个问题,我用了一种方法编出来!
: w$ X* ^' \/ B  x7 P但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, r0 _/ }/ n" {" ~* m" Z
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 5 [1 f# ?, ~4 v  j" z9 j& @6 p

( u( R% b) V6 ~2 c& ~6 I; B7 B$ H# R
                            题目2 W- [* j( E$ \0 {3 O# i
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 m3 I+ p, O+ k& Z! N
第一种方法:利用循环链表
3 k9 L5 _# g5 [5 _( c#include<stdio.h>
$ M( C  [, r- C- P* u$ s5 ]#include<malloc.h>/ V0 r) Z3 g+ U
#define M 8            //共有8只猴子
) T5 l5 ?1 D2 L9 j#define N 3            //数到3只时退出第三只0 J3 Z; ]: N& ~/ ~1 X) `" e2 m
typedef struct monkey
* n: ~8 V9 b* P1 i6 E{int number;
: Z4 f% |! X. e. d$ i1 Rint flag;
+ Z6 i+ e/ {) u9 |struct monkey* next;
- k8 k& ~; o7 Q}MONKEY;
( C7 t9 n% {. b% C- z4 wmain()4 b; v+ I6 \# X0 D
{ MONKEY *head=NULL,*p,*s;4 H5 S8 v# p9 E: S& j; ]: X
  int i,sum=0,count=0;0 `% P+ i6 w- J! W; |
  clrscr();              //清屏
' v/ q6 ~  t1 q7 O  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
9 M! J# v& q; z: w  p->number=1;p->flag=1;
5 Q# K9 a  Q- J% h( [  p->next=head;9 W# N2 N) i7 [
  head=p;6 s5 [) ?8 V0 U3 C+ h
  for(i=2;i<=M;i++)
% ^3 `. p- _2 A) h: M/ ~7 m( @    { s=(MONKEY *)malloc(sizeof(MONKEY));
. B9 {# C# e: N' _     s->number=i;s->flag=1;/ b- l6 s& F, K$ m
     s->next=head;
$ h6 Y0 @7 ?+ i1 c& q     p->next=s;p=p->next;, H4 p# J: l* t, D4 \& `# Q8 S7 L
    }
; N# E, ^7 N# t  d4 H7 L4 g    p=head;
. d! J2 t7 x9 f, I& E6 E   for(;;)
7 e0 r2 _- d. F4 \3 d! J. G0 h5 ^    {if(p->flag==1)  E+ |" W% b9 v) |# E! H& }) l
       count++;  E9 `3 }/ V1 E. A8 \
     if(count==N)
0 x! |/ [2 ?$ X# s% ~        {p->flag=0;
1 A4 ?5 B) }' Z$ o: @         count=0;' o, \8 Z# r5 P2 t
         sum++;}
4 h$ V% f! Y1 L- c% {% u& v* J% `# r     if(sum==M-1)
! R' [( @# `) W  d6 t        break;
1 E, |! M, I7 [- |$ g+ s7 Z. H1 d     p=p->next;
8 K' b+ ~! {* U# w- C4 b3 y    }
7 l% W( q! j+ Z% I5 j# y$ b    p=
9 @: b$ y* m2 a9 E. `    head;
4 i4 C$ e: A, m+ m5 M    for(i=1;i<=M;i++)
% z  J; w6 O# ]% y" N8 `    { if(p->flag==1)
0 v; a# {4 L' z; d1 P; S3 p        printf("\t%d",p->number);
8 B1 x% ^% v/ s: x      p=p->next;- k( t" Q* `6 H
    }
. N$ P& h$ P) Z( G* Q' W' S2 ]' E- R7 i: o

' J, Y0 I  Y; {8 ~( l; Y, L
( `% n8 \: r% Y- k: M# u}
. O1 G4 }2 d3 B( h
第二种方法:数组
7 U+ l% P' O8 P) V4 P  b( Z( g#include<stdio.h>
9 J8 D  {- q! l#define M 8
: M: E- G! ~9 i/ x3 Pstruct monkey
& M. P1 c1 q8 j  l; h{int number;
- x4 r7 F, j4 r  X: R. Xint nextp;2 j! l1 c! C9 o: G* ^+ ]+ w
}link[M+1];
2 K: m. S- p- _* Q$ G$ M$ B
; t# `7 T0 Y9 D9 T! Xvoid main()' @4 F* R& U1 s$ q5 h" r% e- y
{int i,count,h;; J% y& o# r2 t; t$ s6 c3 E& Z8 j
for(i=1;i<=M;i++)
' w. i2 q) H. q9 _: n2 d7 `" c: P+ @& I. K{  if(i==M). `' {- w0 f5 N. \% w4 n. F2 {
   link[i].nextp=1;/ {6 I! m$ Q0 K
   else, e9 B. |, O& ~% p3 Y0 k
   link[i].nextp=i+1;
" ^+ x! S5 |9 F" ~6 }  link[i].number=i;
& F7 A( |9 _+ g- }  S}( H9 m+ P8 l3 @) U- [# b! }( L. a6 ~
printf("\n");
$ z% B1 z0 f9 b; R: v- T" i& Jcount=0;1 f6 m' T0 D& t; u8 h" ~) ^
h=M;
  k3 ~! r$ O: f& I) R0 Wprintf("依次退出的猴子: \n");
1 j. w; n$ `0 O0 {& {while(count<M-1)4 t1 y7 h/ E& F, S( w
{i=0;' W& t* m6 G  w, I. `) d  a' i
while(i!=3)
3 C2 Y2 `; J# ?+ v& q{ h=link[h].nextp;
/ o3 w: C; C! N: n$ I) ^   if(link[h].number)& T4 z0 v. C8 ], e- L
     i++;}# o2 M- E+ X+ |! j2 F9 U2 H7 E  x

  s' T6 h  q* q4 ~( T+ S; M, eprintf("%4d",link[h].number);
& L$ F0 ^! j, U4 b4 Mlink[h].number=0;& H: l! q. b" \$ ^/ ^$ O# \
count++;6 ?+ O& h" M9 z9 M9 s# T0 k2 R
}
4 z  `2 a5 K: h. ]/ c! {( R; r& i8 S: a- J5 s- c" G# |
printf("\n大王是:");
$ b- O5 E) S3 p% \  R& M) f4 L- K  for(i=1;i<=M;i++)
6 l( _. ^3 x' ?2 V) U8 D5 c  if(link[i].number)
: W# e2 ]4 m' {    printf("%3d\n",link[i].number);4 m& i' q# X' B

7 I, \3 h- U, S  f; i* A, t% ^" ^6 c- |! z$ e5 A% G, U# V9 H
}
6 w" i7 _4 a8 {; b% b$ v3 P
第三种是普通方法for循环

3 I! U6 R, m1 D* u% Q#include<stdio.h>4 h- b/ N: T- B
void main()
% h, H4 U/ [- ]{ int i,k,m,n,num[50],q,*p;
+ P. w% {7 n4 W3 r& @    clrscr();8 G0 X- L  R+ J4 G( Y0 w7 U
   printf("input number of person: n=");
0 Y. R: y' x; L6 B! O1 X    scanf("%d",&n);/ }: i; a7 I( b2 [; I, D. O1 }$ `
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只6 G8 d2 H) N$ [
    scanf("%d",&q);; i6 P. m( W9 z: d
   p=num;
# V4 H. ~& q& }1 Y% l  for(i=0;i<n;i++)
* G! Z6 d) J2 `  U; m1 G5 Z9 O    *(p+i)=i+1;
# z2 l9 A1 l+ {! L2 M/ O* [+ O/ c   i=0;
+ _, h2 i4 h) F( u% D  [' X8 ?- W   k=0;
; E  r% h9 N# u" a' I   m=0;! e* z* l. A! B$ f! I9 r
  while(m<n-1)- D$ M& {. A; O$ ]$ k
   {if(*(p+i)!=0) k++;% M( j4 M, g' ^; {# U
     if(k==q)* Z5 F( y/ F" U$ z6 N$ r8 v
      { *(p+i)=0;
/ V* r: T+ X$ u3 L5 F        k=0;. W( r& \9 U4 H6 a
        m++;3 i+ a" w: D: b! @7 v! K
      }
1 ^) w& Y" `: w. S) I$ S    i++;
3 _: {0 }0 n; Y0 D2 W8 H, J    if(i==n)i=0;9 R. ?' z) i5 ^5 C1 U/ [- ?# B  z
   }
" S5 I- u( G) g: {' ^- t* ]  while(*p==0)p++;
8 [! ^- d) A/ `    printf("The last one is NO:%d\n",*p);! t& r& L1 X, l" a: Q- h
     getch();1 Y% D6 c! m4 C" p

: x8 l3 e" A: A2 E4 A. z& E}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 n* d2 ~  X9 b& F! fnamespace 又费马达又费电8 _& U0 a; ^; l( |( U& y+ e, E
{) F8 I* ^. G( u# t. n
    class Program
9 X$ I4 R6 h. M; C" x    {2 L/ O3 v1 Z1 Z6 I3 y) m
        static void Main(string[] args)' H8 t" X, A0 }3 ]
        {" g- Q$ X2 K! i8 |4 Q& `) i
            int m, n;/ [  M7 l9 Q% Z, N
            Console.WriteLine("请输入数组长度");+ H9 C- {; l7 I% u
            m = int.Parse(Console.ReadLine());//m为数组的大小- V. `7 p) l6 [1 [0 i
            Console.WriteLine("请输入要截取数字的大小");% A7 n  o3 n/ v- \. U
            n = int.Parse(Console.ReadLine());
) `. j- U& @8 |7 D! t/ N2 E) Z, j            int [] numw=new int
6 Y3 l: Q$ g9 s, }7 ?
4 w+ q. E& O4 W" h5 E&shy;&shy;&shy;;- o, I. u% ]% w0 k& f! x
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数3 ~  _. e, x6 J6 d9 M- X8 o
            {$ O. q9 |7 t! I5 `1 D$ H/ L
                numw[j - 1] = j;
- v+ i& u4 I. v            }  q8 D9 g- \) X- X' u& v( ?
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
/ R0 m/ x* @5 C. @/ h            while (d != m - 1)+ z! }5 Z( i: q
            {
1 L% P* j8 b6 D- e  T" E9 C                if (i == m && d != m - 1)
: \8 @% M8 v/ c* D  q. ^# P                {4 i3 x2 S8 }, P- x, K
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
+ n: G2 u5 f2 \2 _; z  ?) B  e: I                    continue;
3 E0 P+ `0 I4 I1 m                }8 [+ O. W+ N' H3 Q2 P1 i- S
                else# }6 W% M9 i8 C& i' `' [% J9 H" w
                {
0 A( f! J" ?; |                    if (numw[i] != 0)) P5 O# M  |- ~$ A
                    {6 r. @, Z# G% N) g9 [3 O
                        i++;) T' \! D, x2 Y9 j- e
                        k++;
6 T, F$ Q2 O/ C5 R* T9 a2 `+ e                        if (k == n)
5 W. t; u- s+ Z/ B4 F                        {
  l4 d' Q! d% \! I  R7 n& }  [                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
% [& b6 H6 o4 l9 O' t) |& N+ z! G                            k = 0;
  F( k$ Y3 t* u! |              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
( R7 v, s+ j" k5 R8 k* m                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);. n- {1 x/ V/ p0 r- s
                        }
5 O8 p9 G2 R0 y# j                        else//输出暂时还没有改变数组元素的值% s) o, _# I7 Z% y1 p# _1 i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
7 t4 E' V; _. B9 x, s, {- W                    }5 w7 a+ L$ S, d' o  p/ Y/ T
                    else
/ m+ W- R, Q4 B; P4 P5 f  l                        i++;//数组元素为0,直接跳过,不计数。。。
! W& Z8 L8 H. k( Q8 t* [                }2 ^- i7 _0 R) u' J8 [( z. D3 I" e( Q
0 K( k$ r* k! ]# ^+ e& P0 q9 h

$ K& m6 y) F+ j! }! f! ^1 h& T            }//结束while循环
/ c/ ?6 t- Q( Q/ u            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 P# v4 G. f0 L7 W
           
0 {* h) ?8 S( r' b) W2 o! B" \                if (numw[i] != 0)" W2 I8 f; r( M4 h' I7 \, u
                    Console.WriteLine(numw[i]);
3 `7 w) [; O& d+ V9 L           
$ q9 {5 Z( B0 D2 _  d. I9 s5 M            Console.ReadLine();
' u% a7 j) ~3 @# M1 h- e0 F0 l        }
$ Q$ A7 D# W3 h+ u    }
/ y5 m6 G3 N  T/ h' n; ?: v}1 j) f) }* P% N3 x0 I
小甲鱼最新课程 -> 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-3-3 05:02

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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