鱼C论坛

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

猴子问题

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

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

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

x
大家好!- ]. k, k. R) O6 v$ r5 p3 C# l
这几天我在忙着编一个问题,我用了一种方法编出来!
/ I& i9 A- U. `0 `. s1 ^7 z0 Y但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, g8 d4 l( f, z+ c
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
6 f% `8 k6 A" {- A3 ?1 C& v3 w: l
) B2 l- @( {( u8 u' l. E! Q! F8 R7 n  n5 n. b; M9 `: z6 H8 a4 w
                            题目
3 w0 x2 x* m- ^+ _, D; d8 H山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
  a* L9 J2 C& i6 _  X. S9 r第一种方法:利用循环链表
( X- T6 A) X+ g1 _; q2 J#include<stdio.h>
; C, [. D0 V/ u4 J: ^5 L. {#include<malloc.h>
8 C" g3 B9 s0 V2 S#define M 8            //共有8只猴子  @& O+ w% Q6 `  c+ u
#define N 3            //数到3只时退出第三只4 T' R; S9 c9 W5 d/ ]$ c
typedef struct monkey
0 l) v; P& r; b( p% }: X5 [{int number;2 h+ m8 c& p7 b8 z" Z  e! p3 A; }( ?
int flag;# Q' T) N: i* G& O
struct monkey* next;+ J# q; w7 w8 y3 R/ Q
}MONKEY;. U6 |3 Z3 F0 E* v. n
main()/ y* q. c$ _5 U& }( n
{ MONKEY *head=NULL,*p,*s;+ D2 S) z2 H) {" a4 V
  int i,sum=0,count=0;- j) y  \) i* T2 z. f& f
  clrscr();              //清屏
& k, u# w% G4 M1 A% p. t3 v  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
$ G3 i9 C$ J  \2 h  ?) j: _/ C4 c7 R% n  p->number=1;p->flag=1;" ]+ y6 q8 z) T5 E$ ^; ]4 U# P7 h
  p->next=head;; t4 U3 _4 ]2 @" L
  head=p;5 Y! d% u( S2 D9 H
  for(i=2;i<=M;i++)
. d3 M  S+ s' X( _- k: i$ R    { s=(MONKEY *)malloc(sizeof(MONKEY));; z# s2 T: S: m# \
     s->number=i;s->flag=1;+ A8 B8 l: n5 g& [8 j5 k
     s->next=head;  }. O# Z0 U- c
     p->next=s;p=p->next;
, B7 K. \2 o4 n) S0 C    }
: G4 v/ I9 g' ?4 T% B    p=head;" S* _% @* F0 I$ C$ X/ _, `
   for(;;)1 G1 ~* v: U. V
    {if(p->flag==1)
' p" k+ p( ?) T$ z/ v- D8 Q# {8 p       count++;
. _' n& D. Z: V2 E' m     if(count==N)4 s* @+ F, w' q+ ]( i9 D
        {p->flag=0;
4 L/ E; k: t3 J4 F8 e         count=0;
3 y/ k* ]0 K8 Z1 |' [2 g         sum++;}+ Y" |; B: f& V+ j3 H4 o& T
     if(sum==M-1)
: ]$ ?$ |4 Q0 u1 d3 \. v) h0 B: T        break;$ ?0 k$ n# d4 b+ U
     p=p->next;1 @. C4 H0 r( Y& D
    }
$ u) W/ F4 g! {5 [# b    p=8 j$ Z" Z3 }) R4 d
    head;% r5 h& z  P3 I+ O' \; V- V. f
    for(i=1;i<=M;i++)" n4 Z' u/ x4 B" D% w
    { if(p->flag==1)/ i5 I2 Q: x" Y1 }' W% V$ U& V1 _7 H# p5 D
        printf("\t%d",p->number);
, G6 e9 z) D; V      p=p->next;- z! d7 d) q# O' S8 H7 d
    }
5 }4 q* a9 p, e2 n. A& H. q, W' [5 t) r$ }

  Z6 s9 ]* A1 W- g' }8 R4 S& m
8 |1 y% E7 x! u) n( P% h/ D' z+ F}
# v0 u/ G7 z4 D+ `/ K
第二种方法:数组
; i4 Y) R9 b+ k* L3 [- D8 ^' A8 y#include<stdio.h>
9 t9 ]4 t7 _8 b/ `#define M 8; ~0 C( g, I- f* i- Z( O: I3 B& h
struct monkey
( N6 J0 A$ g' ^{int number;
& r6 l& D  T  r8 [% a9 e6 r  x" Bint nextp;
# @, R0 ?0 q; c}link[M+1];
5 D" e3 P. p% Z& L) ]8 b& S: o
6 ]- i$ s4 U9 H1 A% u: i0 Mvoid main(), z0 V6 o8 i% b1 g- J7 K9 V
{int i,count,h;6 E2 w/ t9 H; }( i
for(i=1;i<=M;i++)
9 E2 A7 r; o$ x* g$ e{  if(i==M)
/ \1 m& M/ {1 [0 e9 T8 ^   link[i].nextp=1;4 W. y8 c0 w* k9 r! H
   else/ z- T, ]0 h/ O+ k
   link[i].nextp=i+1;
2 h8 w9 j- a( w* {# g! n# r8 i  link[i].number=i;
+ T0 ]( I, ~1 U9 z2 |}8 C& E9 `1 b5 X/ s8 ^8 j
printf("\n");
, s) r5 X  F$ Q" ]% r5 ccount=0;
. c' _7 c  p7 c0 _h=M;
% ?2 f4 x! S: @printf("依次退出的猴子: \n");) y& P7 Y# `& X/ W
while(count<M-1)( @' j9 |% I" J/ |0 t- U
{i=0;
" Y1 @3 s: c" V1 o* \2 x9 Kwhile(i!=3)3 l  r5 g+ D$ {2 z* s* z- Y) a4 N
{ h=link[h].nextp;
, ]- i: k( O% o, R+ ~   if(link[h].number)# M% Y* E8 R; B" C/ R- x
     i++;}
0 M0 c+ b. A* B$ d9 m1 \5 _4 b1 ^1 c: Y. n) E1 m, N+ \8 V
printf("%4d",link[h].number);7 P7 E7 W) _8 o  N$ z' Q+ z
link[h].number=0;  \' j. U8 n1 j
count++;* m0 E/ x2 I) s% q
}% c/ V1 ]: Y& v* k4 L

- N, x! J+ }0 N0 }) n0 h  }8 Qprintf("\n大王是:");
7 e- @3 y& O8 y9 e# ~  for(i=1;i<=M;i++)2 e  T, J% H  n0 o
  if(link[i].number)5 z% B  f# t2 Z
    printf("%3d\n",link[i].number);. U- n/ z4 m" u5 d
# w3 Z9 A( ?% h( {, ^

% e3 n% l* l- i) [; l}
$ {5 b% L. ^4 ~) {
第三种是普通方法for循环
, ?, ~: K* C& }! ~4 w7 y
#include<stdio.h>
! V. p/ |1 C8 c' w3 G( wvoid main()
9 }7 _  o% _! X  E{ int i,k,m,n,num[50],q,*p;
& {' y' M8 b# }) }1 m9 W+ k5 c- c    clrscr();# W" ?. n- A; w) K3 w* o
   printf("input number of person: n=");$ {% _0 d( g: d' ^, l$ Q
    scanf("%d",&n);  F4 p! W( ?: T
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: Z) F# {9 v6 }    scanf("%d",&q);
% m& a3 A& a' d6 l   p=num;7 S! C) E  E7 |' R- \% P0 w- m
  for(i=0;i<n;i++)
  z5 R& [9 l, \    *(p+i)=i+1;
: P1 ^6 q/ d! v" E( Z. L$ j1 O   i=0;
2 P+ g3 `" l6 q( ]# \; h   k=0;
. W2 C+ H4 l6 k( n6 m- Z- {   m=0;
6 E: @; |: }6 |* p3 M# U  while(m<n-1)
3 }5 A3 Y& N  C/ o0 D0 K% i! r7 J   {if(*(p+i)!=0) k++;6 ^+ t5 V" ]2 `, U# A6 F6 g
     if(k==q)+ F6 l! G6 R, N6 O. {
      { *(p+i)=0;" b# ^7 E/ D+ `% v9 N7 \
        k=0;
$ U! }' X& ]5 v8 E& l        m++;+ b7 ~( H* h5 X  {$ K* Z# U
      }
& c( f( T) X+ z# E& L! v' j: d" j& M    i++;% Q* ~0 U9 r" Y) w
    if(i==n)i=0;
' N( c9 T2 d: i# f+ V   }9 q) e  u$ s; i6 C( f& M" j
  while(*p==0)p++;" X0 {5 n2 d) z" n3 F
    printf("The last one is NO:%d\n",*p);. h1 X9 Q; k+ o
     getch();
+ x% X% g% @/ `4 i, l0 y( X' w* `
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;, i, Y, q% ^; y8 P
namespace 又费马达又费电3 p8 [" `1 [+ Z5 c! z) e7 ?: v
{
# q& g7 S/ h7 p6 d/ i    class Program
' E) e0 A- d, i' s/ D3 B    {) }6 d* G1 h, R- x9 ?: t! ]! C
        static void Main(string[] args)8 N5 r4 o) M. b- \) V
        {
8 c& H1 f; u& S( }: D+ _            int m, n;  [0 p  c$ Y0 O" y& Y) ~' O2 W
            Console.WriteLine("请输入数组长度");- K& b/ |% F- {9 q
            m = int.Parse(Console.ReadLine());//m为数组的大小
) e' P+ M7 m5 l1 S' n            Console.WriteLine("请输入要截取数字的大小");7 K6 a5 \& b8 s+ e
            n = int.Parse(Console.ReadLine());  t" g: ]/ t; e+ a7 g: g$ S' W
            int [] numw=new int
4 F: U8 `  G! W' [# P
& ^% D$ N- e# g' t# S5 J/ s&shy;&shy;&shy;;
. q9 A8 k  o; I% |2 r* O" e% C            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数. [( I. L8 V0 F' G& D! |1 ]" N) F/ M
            {
9 ?9 q- A& Z$ e" }" k                numw[j - 1] = j;
1 J6 p7 ?7 Z" p6 w            }* H# S: w4 ]# U1 q. S; z
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
5 w7 }1 R; T' n: C            while (d != m - 1)
7 f: c/ q( V: `            {% H8 S& {- d1 m) W) x& p: y
                if (i == m && d != m - 1)
8 Z( X( [, Q; \; n                {; K! k; J7 a1 f8 s
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!* _2 [9 _9 ]2 l7 L& e
                    continue;/ |; |* `$ c' ]* o( w4 X
                }; C& u" l( W# p3 Y6 r. E' ^
                else
7 Y  l+ F4 j- Y- O, k% q                {
+ u# U" D* }1 }! G  {                    if (numw[i] != 0)
, X1 g* _4 R% y+ _7 [" K7 w# h                    {
' d# j1 ]& Q! {, m: S, B                        i++;% M: [4 Y  k: h$ I7 {
                        k++;
: {4 F' ^& Q$ y" w, V                        if (k == n)
" f$ B6 c% W, N9 i% `8 H' o& E7 A8 }                        {5 R$ t3 N& Q0 x: v4 c5 n* N$ a+ Y% [
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& s3 b& t5 v6 ^8 G! V
                            k = 0;
% i* d- g, l2 ~2 z7 b              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
; `: T; m* e$ D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# [, }: Q5 P+ l                        }
$ }* m9 a+ k5 w* n- n                        else//输出暂时还没有改变数组元素的值% l9 ]  N7 ]/ c
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ _. ~$ l) s( Z+ T! k6 P5 ^                    }
' }! R3 _2 A: t3 r2 n/ b                    else! O# i) o! m! {2 K2 {8 ^& H" b4 [
                        i++;//数组元素为0,直接跳过,不计数。。。
" f/ f. h' j$ H# U2 `: y, Y- X$ v                }+ u: w7 M0 I: N7 q# r

! ^3 U+ s1 W" g4 Q
! o) q7 b1 C  y            }//结束while循环
, J$ _2 d& }7 ^7 j            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦: V, ]8 i9 o8 n2 m# ~3 U
           * u, X7 ~) y* J/ Z2 t
                if (numw[i] != 0)$ j! [8 g2 h: P# c2 ~
                    Console.WriteLine(numw[i]);
8 x4 P% K' k3 b9 o8 K' G( w6 j; s+ M           5 c6 r  z& L) j- @( w7 \
            Console.ReadLine();
6 z) F3 b9 {) G* s+ e        }$ O4 |: y1 i2 t
    }
$ V# j+ }6 M" T5 P) s}
: g! f1 A. F# d
小甲鱼最新课程 -> 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-12 06:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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