鱼C论坛

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

猴子问题

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

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

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

x
大家好!
1 P# C$ e% Z+ a这几天我在忙着编一个问题,我用了一种方法编出来!% M' c; `1 Y( i
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!) w, d+ H& m# b+ h8 @
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
* w3 f3 v" l4 y# C
( P" T( [7 l+ c" s
, _1 ~& _' u1 D8 n  `0 t4 ?
                            题目
+ M0 Q0 O' ^! x& r5 C+ P4 X- t  m山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
1 h: ~. J) p% a第一种方法:利用循环链表9 P$ R0 R' E, i& o
#include<stdio.h>; F/ V# g  `9 b4 x3 p& @
#include<malloc.h>
! ?/ `+ z2 |9 O; w$ C( B* |6 \#define M 8            //共有8只猴子
/ c) ]/ S1 c; H$ K; v#define N 3            //数到3只时退出第三只0 ~9 ~' g7 S' q/ N+ e/ w
typedef struct monkey1 _2 G! \/ t2 e, }3 `1 f2 d
{int number;% L8 ?# x. m/ `
int flag;# C3 Y9 [5 w' i0 [5 i" a
struct monkey* next;+ v6 L' U- H! G9 a* T  J6 q
}MONKEY;
: M) m/ F0 @7 i1 ]# E3 s+ j5 Amain()
1 {! x! h& Q+ t3 K! _% u- S{ MONKEY *head=NULL,*p,*s;
7 I7 s) P; A+ _" b8 n# Y  int i,sum=0,count=0;
! ]% F5 C; x( g2 z/ h& g5 v  ]  clrscr();              //清屏! J) s% |2 S6 k: ?: G
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存) T$ n0 o( U. ]$ e9 M9 J0 N
  p->number=1;p->flag=1;# s7 J. B3 i7 a, E' @' D7 X) m- c
  p->next=head;. r0 f' j% P5 ~6 j% C! l6 V
  head=p;; W( x% `; h; ?" A& d! g/ g8 i* t
  for(i=2;i<=M;i++)( f  S3 k/ [( [) s8 z* h
    { s=(MONKEY *)malloc(sizeof(MONKEY));
/ S1 O& {! a+ z3 ?0 E     s->number=i;s->flag=1;
+ N. b- j" d5 ^     s->next=head;
* {( i7 ?9 @0 R     p->next=s;p=p->next;
* P8 X* G) F- z2 A! @2 i    }
8 B( x3 V) q/ B, p3 J7 U    p=head;
+ v' j- u! P- Z* o3 |   for(;;)" z1 D4 g, A& R* \; C
    {if(p->flag==1): o6 F+ z8 @- X3 p) Y
       count++;
- {) D4 V/ a+ D. m     if(count==N)( z2 F4 r- P3 [' R7 f
        {p->flag=0;
2 Q+ z: ]% I7 B6 O! Y  e, X8 s. r9 i         count=0;
/ i1 f- e6 [! W3 ?, ?2 f2 ]7 a9 ]         sum++;}8 h0 B) n4 Y$ `0 P5 w  l1 R$ G
     if(sum==M-1)
# L- q! i8 `  _( {' G7 g        break;
# E( ]9 b4 ]* M     p=p->next;
6 U6 j, t& f9 `. k. E0 J    }
% k9 I9 K  R! |* d4 P1 L    p=
5 `1 {) ]8 j" w: T5 ^+ z2 t3 o    head;
3 `/ E! v# a9 }7 J) }$ O! A    for(i=1;i<=M;i++): _: g+ Q0 ^  A1 \- a, f
    { if(p->flag==1); t( x8 R. P  b) F$ o- ~
        printf("\t%d",p->number);, d, z# {$ |# w2 l! u0 n0 |
      p=p->next;$ @* ]" `* Q( H! h
    }
0 A) j0 I5 O, J$ g! V9 G8 n6 C, Z0 o! {
9 i5 D$ }# L. j) }0 I: Y5 B

8 i" p3 r6 M/ ^. J* o9 z4 [* R}
; O$ p0 y  S8 k& ]/ Y
第二种方法:数组% D& P9 e1 ]& C, a4 t. P
#include<stdio.h>
3 y& F; W+ Y, \#define M 8* l8 [( `: H( ?* j3 g
struct monkey
" @  l. N9 \3 k" o& C{int number;3 h8 o, g- a  m. q
int nextp;
/ F0 I3 ^- e; W}link[M+1];# x% h/ t$ C) _/ U" G- q9 j

- f7 F- I: j7 ]1 @  _+ ~1 ?- g' yvoid main()6 f4 f- A1 Z! n2 j9 w
{int i,count,h;8 d  a2 ~0 z$ r; ]
for(i=1;i<=M;i++)
! Z3 E# G. p; N0 y9 s{  if(i==M)% h6 k, R( w3 q" t: e& r
   link[i].nextp=1;
' [  C1 N+ F% W9 w( G   else
) V* @: r+ n6 Y6 E$ f: i   link[i].nextp=i+1;! p! O, c% x( f6 m2 s5 e
  link[i].number=i;' f7 m7 k: B$ U# J' }
}$ y% V  D' X0 R- Z% K+ O
printf("\n");
  A- _* e, I7 Y8 x) Ncount=0;" n8 Z+ j2 W5 W5 M
h=M;% H0 \1 o* D& i& P) `; j' Q# s
printf("依次退出的猴子: \n");
' @6 l+ z6 a; r1 swhile(count<M-1)7 j& L6 b7 _* D- ~  [
{i=0;( z4 `" @' C5 u6 {- U1 m, x  ?
while(i!=3)
1 h/ m& [3 d7 O: E8 b{ h=link[h].nextp;1 a8 n% \, f0 `7 j8 \7 S
   if(link[h].number)
+ D% |( w5 {3 y* o5 M     i++;}
- U1 L1 O) A0 G0 \5 x7 i
9 u4 q( \/ r1 E* m& yprintf("%4d",link[h].number);
. [+ `* ]3 H' w4 |' W! c$ Rlink[h].number=0;, @' M) A: I% w! {- ?4 t& n
count++;4 B, Y" [5 y; ^2 L, }
}
1 ]) ~$ G7 {6 T! Q% i- [! p2 T6 u# x6 Q% E6 n/ x
printf("\n大王是:");
2 U, G. l+ b9 P8 H1 O( y5 f  for(i=1;i<=M;i++)
9 h, H0 S9 M- `4 O  if(link[i].number)3 C1 X4 T+ H; W. L0 U# y5 T2 \
    printf("%3d\n",link[i].number);, @! ?1 n4 P" Z- ?

$ ]: y+ U! V8 x& H* P1 C- B0 t9 H" z& u0 w8 l! ^  ~
}
3 l1 Q; O  g: B* f2 N6 T  r
第三种是普通方法for循环

9 L8 k2 F7 Z& R$ I#include<stdio.h>1 g5 l" K- c% n* o
void main()
1 x! e! I+ H) Y% _+ G{ int i,k,m,n,num[50],q,*p;
; D9 Q# i  I9 n6 o0 \* W8 v    clrscr();, f6 ^! {. G& r; Q8 l1 G: S* E
   printf("input number of person: n=");
; g- {- d' D0 o/ d, R3 A- B! V    scanf("%d",&n);
( r% [9 [- X5 D! }* ?* uprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
+ q" t+ M3 v  @* [4 M0 f( v    scanf("%d",&q);
/ z) R1 D+ Y# ]. ^  g   p=num;
9 ~. F! L: U  c$ Y8 |7 Q, J. V  for(i=0;i<n;i++)
* }3 z( d; J9 g$ A9 q7 F; B, F    *(p+i)=i+1;; S/ [2 ?- U. x
   i=0;3 [+ N6 b- o( W* W" s
   k=0;" ~( J' r) ]) F2 o7 H$ D
   m=0;% t/ z. i$ ]6 x
  while(m<n-1)
$ ]7 L: j1 a8 u: `   {if(*(p+i)!=0) k++;
- M. v1 n+ o$ I     if(k==q)
" z+ D* H. z+ K: a      { *(p+i)=0;
  K6 L( c& j; P1 f$ a        k=0;) s: ?$ U8 }6 z9 p. t
        m++;8 B7 v  D, Z( O: K6 p( A1 L) m
      }$ ]  V+ a) z" F$ s; n, T
    i++;
: S$ |) a5 u6 y2 r    if(i==n)i=0;
. b/ y$ [- d: b: Q   }
" J, Q4 ]) @% \) M, f( [; G; W) A  while(*p==0)p++;; O/ v& i) ~* c7 W+ ]' `; Y
    printf("The last one is NO:%d\n",*p);
' ?) u  C+ n1 z& U     getch();) W( t  |! L% h2 L' J2 [2 k4 e

8 e' z$ p5 w) Z- V}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
  B7 R; v; D- U; E! i% }namespace 又费马达又费电
- p% Y# @2 y# f  e+ y{$ W' U& l4 A- y! o/ U
    class Program
, T( m7 ]6 M+ b3 d    {
1 u% S/ W3 B1 b* [1 s) y4 I        static void Main(string[] args)
9 m% {+ @/ z* F        {/ W' f% m- k) l7 A" Q
            int m, n;
  v8 {8 H7 F( J* r$ ]0 D4 U            Console.WriteLine("请输入数组长度");
" `/ J8 D( z* ~) _            m = int.Parse(Console.ReadLine());//m为数组的大小
( \% \; I( m# s: y' W            Console.WriteLine("请输入要截取数字的大小");4 I) k* W6 _3 P8 Z
            n = int.Parse(Console.ReadLine());& ]# P& p* ^* I2 g, R# `% O
            int [] numw=new int
/ f/ A0 t& X+ |" K, E: H4 k8 [4 [& N7 ^8 |7 |+ d* M
&shy;&shy;&shy;;
, d3 F  u+ d  N4 D2 B% I            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
) h: {& g; r2 Q( n! |# d, f            {" }, X* i( D! O* U
                numw[j - 1] = j;( J7 Y& ^% J$ `; F3 T
            }
3 T+ t8 B# n' I2 [4 z8 F! l            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! q; i2 ]% r' l4 O: v, {7 y0 r
            while (d != m - 1)2 D( P% _; a9 p
            {
# J$ E  P* `6 X. f. z                if (i == m && d != m - 1)9 {$ q* c: ?  L/ ~. m6 ^
                {+ g; w+ F) i& o
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
: _6 \7 m6 s* |3 E                    continue;5 ]: H( q% b# a! t/ v
                }: L3 v  E4 L. T. q: q/ \/ u
                else5 {8 [; S. X1 W8 c0 P9 ?
                {- }5 t! H: H6 z" h% o- M
                    if (numw[i] != 0)
9 \5 W9 U' U# d) Q                    {) M& E, q5 o, c0 g
                        i++;1 Q# Q* Z; F4 h$ e( s
                        k++;1 f* ]' z2 w5 T0 v6 z' H
                        if (k == n)
" y: p) a- v7 A( L                        {! k, c7 n! a1 }. i1 L) ]9 {8 _$ r
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
. n7 p' t. g3 ~, m                            k = 0;  e" I" c8 K! j$ Z/ o5 K3 o! M
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& A, x; a; r  @
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; s6 M4 o( |  L, F5 u                        }* d! m4 ^' S. {5 M
                        else//输出暂时还没有改变数组元素的值
* k6 D' r6 W1 {* d" F1 F7 _                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
1 F7 M/ Y$ V# I& a5 [- X, G                    }: k0 Q  ?( y- r" ?& A
                    else; q$ j9 E! `4 `" E
                        i++;//数组元素为0,直接跳过,不计数。。。
* D1 I  x0 b4 q6 U  J  Q' P4 A; e9 O. X" j                }
9 a* O) c  }* f! \
9 F+ {# P+ j8 s* ^3 |/ H; |4 v9 f* R  [8 i
            }//结束while循环
( V  D# B6 [0 K6 K6 X) u' j7 |1 e            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, b4 t" n, ~% X* I* r' V3 A           7 F/ O  q( I, G+ d) c
                if (numw[i] != 0)% j2 _' u8 a% U6 ~
                    Console.WriteLine(numw[i]);
! C2 ?% a8 N& \( [5 ~7 @" y           4 c3 v9 [( p1 Z0 e' u
            Console.ReadLine();
6 ]  O- m1 l" b        }- A, r! i: z+ A+ B" E& o
    }* k, N) V; S6 }$ U5 A  _' |) A
}' s% \4 z) |# q
小甲鱼最新课程 -> 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-27 06:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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