鱼C论坛

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

猴子问题

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

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

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

x
大家好!
0 e5 y. F; i% x0 a0 K这几天我在忙着编一个问题,我用了一种方法编出来!! r+ x2 v' C  [
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ Q# e* b: _3 d* @: }
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ) H- }/ @5 N& E- }" \, |: x3 }! P

& R6 C2 ~& r( X. [- w2 `
5 {& M, p6 S0 x# _+ K& X" @
                            题目9 ]9 U2 p* a# D) s1 G( w. a1 }
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
4 C) P: H0 M% s0 W2 }7 }% }. Z$ U8 X第一种方法:利用循环链表
/ b8 [* t+ t  F& X' M; I% s#include<stdio.h>
; D& J9 i% e) R3 X5 `& h1 r#include<malloc.h>
7 M" i' a) ^6 t! c& @& |. T# d#define M 8            //共有8只猴子1 U7 w' |" p' V7 |
#define N 3            //数到3只时退出第三只4 T/ H: q! @) D
typedef struct monkey
; `& \; {, r( d8 C! N{int number;5 c) A7 c5 X; t, c3 m
int flag;
) Q& L- h" s$ L+ U# T4 v" C( C, S# Ostruct monkey* next;8 j8 L6 @5 a6 H! ^
}MONKEY;, p7 ^8 @* s  D/ H/ L; n
main()
0 P' ~. B8 f2 L# |) m% P. Z( X4 D+ k{ MONKEY *head=NULL,*p,*s;
" j0 e' b0 C% j; |4 a  int i,sum=0,count=0;$ }; d" c/ B7 E  A% R9 I
  clrscr();              //清屏
- d  C+ U) W* s8 M  W8 A! I- H  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
0 j. O* C: ~- j; h0 i. N  p->number=1;p->flag=1;
* }! w: \% C4 f6 i8 h7 o  p->next=head;; x+ r4 C& I4 J$ G$ z1 D  @1 Q
  head=p;
5 A" j! |0 u+ j  for(i=2;i<=M;i++)4 W. j& j, ^! |
    { s=(MONKEY *)malloc(sizeof(MONKEY));6 X- f% l" b9 f# Q
     s->number=i;s->flag=1;
2 p7 P1 h& ~' b% U7 w: s) N     s->next=head;
/ n' u9 }. n( `" W+ f     p->next=s;p=p->next;
1 A+ Y) y; Q  v) V8 Z' d    }
7 O; a6 r$ u3 V- ~    p=head;$ w) }! Q$ U' M. B6 ?* O$ m
   for(;;)
0 o" t9 A8 d6 ?& P' s  ~" n& D' ^+ K    {if(p->flag==1)" Z& A! O) C* @0 |) e
       count++;/ P. k9 E1 K7 X8 A7 d. }: \
     if(count==N)
- f& i" |& v$ M6 h+ G& ?        {p->flag=0;( ^0 [5 _, q5 r- L$ ~) c; f4 D
         count=0;  S" L0 n9 ]0 g% |  J: n
         sum++;}
& T; l' g" E/ G) Z% d+ u     if(sum==M-1)4 Q/ B; L+ n9 N+ b+ N
        break;& |; I" k4 [+ G: U9 f
     p=p->next;) A+ _; ~6 L% p1 _# ]. y
    }
3 b8 F* q0 t' Q& s/ d7 D1 {$ ^    p=3 B3 m# a& ^  U3 v3 M
    head;9 ?5 o& y1 ~) E1 b
    for(i=1;i<=M;i++)* m- U4 u: j8 ~) W/ D
    { if(p->flag==1)* I0 t: }7 S) m3 ^* g' B
        printf("\t%d",p->number);
0 ?! Q0 p0 s8 t) n* o7 {      p=p->next;
; Y5 v# v' A* V6 F- f: c    }
/ i: P  b$ f3 G5 @3 z5 A9 w3 c' R3 A# E3 y
( [  N3 W6 q- j' d
: Q0 W0 E! ^5 @; J$ m. U( P/ O
}
! j, e+ n0 ~$ S. y- `1 a
第二种方法:数组
% t7 O8 Y+ P, F8 [& A2 R- M0 O& E#include<stdio.h>
$ W' S4 ~& N& G. a#define M 86 \) u8 \$ d: M/ T& `" J: T- I
struct monkey7 {6 q" c3 F& e8 v
{int number;5 [/ Z8 G( v) m4 |( w  @
int nextp;3 x* k: H5 ~* s
}link[M+1];& y. @4 @, H! P: G0 r8 s3 }
' I+ `" G* s( l# y$ o& `! ?
void main()
" I2 H2 l0 D2 _: X2 ~' X{int i,count,h;4 y0 Z, ~/ Z, s2 m* @1 T% w
for(i=1;i<=M;i++)4 ^* X3 h- E# E- i7 q
{  if(i==M)
! }6 X1 `# n/ W5 `' Q   link[i].nextp=1;4 Z- c/ n# p! I' D0 k' z2 ^2 v* H4 H
   else
8 g) Z, n* `9 o   link[i].nextp=i+1;
1 n1 n. u: q( j1 e; Z, a. k% P2 {7 X  link[i].number=i;: X- }2 c; t6 a. Y7 y3 p$ t, e7 u
}
. e+ j! v4 C0 uprintf("\n");
7 g8 B# R* k7 |0 b+ S/ z, Q, Gcount=0;
  K; o' x5 V% m0 s- @h=M;
" C- i' A# }; vprintf("依次退出的猴子: \n");- p8 p$ i8 `: o, M" [) `- v
while(count<M-1)
2 c6 I2 y7 ^8 T! d: M2 I2 ]4 F+ e{i=0;' t6 G- }; x8 c* V* s7 n* N" E
while(i!=3)$ F& i) J% y; F0 n5 q9 W  \8 f: G
{ h=link[h].nextp;" y! A4 ~3 X; G) m
   if(link[h].number)2 E/ F. U  Y9 W$ |
     i++;}
, a0 k' ]+ J4 @# ?( V
0 Z' N: q6 |% G& [printf("%4d",link[h].number);. Q3 E" U: v! T; o$ _
link[h].number=0;" ~0 A* Y9 T* ^/ F: K+ F  y
count++;
3 W; ^8 h; ]) _: G/ Z8 d! I}/ R0 U( N; z" g- ?8 R+ ?7 i  C

; H3 d4 i7 a* s$ a# rprintf("\n大王是:");
8 n9 h7 C' E3 ?% P4 q$ K$ r  for(i=1;i<=M;i++)9 T  S) c* y, ~2 t
  if(link[i].number)" G0 G( Z7 P$ d& ^
    printf("%3d\n",link[i].number);; w' q8 ]3 y' I% J
! v! n+ F" ^5 z2 K& ]

1 \1 P. b  Q3 W}
/ r3 A0 q  m& U/ G( R
第三种是普通方法for循环

' J& ?7 {9 m2 n: ^2 d. ~5 l#include<stdio.h>
$ {% M7 e2 |9 f% `void main()
3 @* l+ W9 J" D6 k& j{ int i,k,m,n,num[50],q,*p;
/ @4 }9 W/ ~: @4 f5 Q6 g    clrscr();+ [* k0 Z$ D2 f" i0 r: T
   printf("input number of person: n=");* d8 E: x3 y1 {: J
    scanf("%d",&n);
, m8 V9 M$ h9 d4 R4 hprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% p1 I& Y1 n7 t1 l$ ?2 Z
    scanf("%d",&q);; H; k0 {, X) g9 m: n: e
   p=num;& F" [$ g/ @% a: b8 E
  for(i=0;i<n;i++)
4 I& E- K. i4 {# i; u6 ~    *(p+i)=i+1;! u1 Z. R8 e; D5 F* k" h1 [
   i=0;1 ^/ P. ~3 x0 i
   k=0;
- M7 \' u& _' o  w5 E   m=0;
/ @2 s2 ~) M+ @$ o2 G) R  while(m<n-1)
. _( n8 ?' ]$ u1 |2 M. E   {if(*(p+i)!=0) k++;5 a1 ]) I, e0 p3 n, J
     if(k==q)
, s, J- h7 |/ T% w  ]$ K' E      { *(p+i)=0;
" s( Z% p/ Q# Q0 u% P1 \        k=0;
6 ~9 y/ k/ E0 h* _        m++;3 L! b; J/ x( u+ A1 z5 {
      }( I# a# ?) R% a: @1 ~8 k
    i++;
, f* ^- M8 u) b, B    if(i==n)i=0;
" `5 |6 S; d* r6 C   }' O. j7 o: m8 U) {7 X& S# b
  while(*p==0)p++;
# w$ u. J3 h: P    printf("The last one is NO:%d\n",*p);
1 ?& y+ X! i; G* E6 Z     getch();( e# I# E" M6 g5 f) j5 S, ]8 J, _' r
- j. j1 D3 V7 m7 Q! ?5 Q
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
: h- [. R& L  r! O& ^$ Xnamespace 又费马达又费电
5 g- s7 g. L* Z9 V; L{) W  i- v) y, _# p+ Q& w
    class Program0 {( H8 A/ V6 U, R. o. {0 Z
    {% ^; X% K) e- u8 }& X2 C
        static void Main(string[] args); b$ s% X" y2 f6 {4 ?2 a4 H7 v
        {
" P# A" P  n* E; u: y            int m, n;! A1 L+ q2 W& W7 u& T% F. Y% j% C
            Console.WriteLine("请输入数组长度");+ s! w2 B  A" X: ]8 C: U
            m = int.Parse(Console.ReadLine());//m为数组的大小
  ~; [! \. R( V, u            Console.WriteLine("请输入要截取数字的大小");
6 `- ]; X+ P% [2 I1 m3 _            n = int.Parse(Console.ReadLine());
. \& w- N, V8 X% M/ [( x            int [] numw=new int' ^9 z* V/ `) w. Q/ m) A0 l
$ S6 ~% g3 |$ ~& j- ?8 W5 H: F$ p
&shy;&shy;&shy;;
6 r3 E7 k0 F$ A/ f            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数' {6 [! ]9 c2 b6 `% i9 \  E6 x
            {$ J. m- U( F- m( o7 h8 ]
                numw[j - 1] = j;
% V' r3 U+ [. X; k9 s& Z            }# @3 A- N! b1 t& S: [* T: d
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
  k2 I( E- ?8 p- e: d; h" B% w            while (d != m - 1)
+ @3 B" X& W0 C            {8 A* j) c0 k) v: b
                if (i == m && d != m - 1)! x# P  ~  \- m  D* `6 ]7 a% {: R
                {
9 V! I2 ~1 R& ?. s* K2 p                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!: W* j8 ^# ]  g: u1 G: l
                    continue;
5 m( _+ i# J8 y- {; l# d                }
1 u6 o- i0 x9 r                else
0 y4 S3 h* S9 l% O                {0 [' b4 ?5 j2 B0 o5 a8 D! l
                    if (numw[i] != 0)
' I- X7 O0 _$ S3 n. ?                    {& e; Y' [* g9 x" i, Z, O6 x9 W
                        i++;! ]& ~, H( h7 L! n6 N7 l) P, L
                        k++;( M, P9 K/ n4 M4 j  c: J
                        if (k == n)0 P- [; j4 e3 i+ ]( a
                        {
* V, ?9 i2 v: w                            numw[i - 1] = 0;//把在n位置数组元素的值改变了9 p$ h- v# w; L; Z( g: I* x
                            k = 0;
! z6 u0 [" w4 X5 j; B              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小17 [' x. w0 |# U# {' a7 A6 _; @
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 ?+ Y! r5 V9 B: V/ p* D                        }' {, A2 q0 H. e! s7 C+ G9 x
                        else//输出暂时还没有改变数组元素的值
, R& t$ J$ N0 w1 Q4 \* F                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
" J- q. T/ }9 A( b! B! w# i7 M                    }
' ^' n5 `9 D6 T) L# o5 F3 z                    else- W& ]4 z0 E# y* s* f; z) F+ }/ |
                        i++;//数组元素为0,直接跳过,不计数。。。
& }$ q# Y0 o& {. f+ i* G! L5 ]! W0 G                }
, e' c5 Z3 T$ [  N& B
' i8 H# q3 Q7 K8 }3 `6 e% i5 x, n# T
            }//结束while循环$ q7 B0 B0 r2 {$ ~' J5 C5 z
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦9 X( l- b- P, T8 v
           
% D. _* V+ X& U, I* g- I                if (numw[i] != 0)
2 `9 E4 {4 z* G' D: t% @                    Console.WriteLine(numw[i]);3 f5 m! a6 n& @* \5 K
           
9 n- F' T5 @- V, S1 `            Console.ReadLine();
8 K8 Y+ ]2 D6 ]! }        }
) p' Z& Z0 V, h; t7 |6 u8 w; ]. B( P    }
+ }, ?0 U, t- N! x- k# P2 t}8 Z. h: z5 J& ~9 ]) o
小甲鱼最新课程 -> 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-7-15 22:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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