鱼C论坛

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

猴子问题

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

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

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

x
大家好!
  j1 y- H) W( ?% V* e这几天我在忙着编一个问题,我用了一种方法编出来!# a$ x% y1 l" s+ P9 W
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
' c2 l% g) {7 ^注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 % H; O( a- q5 V( o

; H! v( q- v1 ^. t1 I! K5 ^7 X8 V4 J+ m/ y. S! g+ f% f! r
                            题目- g" S" O6 \1 Z$ v( U/ z0 c6 X
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
. N) j& W; M2 Z$ I4 f5 M! G! F第一种方法:利用循环链表
) y# ]( n4 b, K0 `! _8 V#include<stdio.h>5 [: Y5 S' P3 M1 Y
#include<malloc.h>
' G( W8 A4 r/ b3 |& W3 j#define M 8            //共有8只猴子4 h" J; r1 n6 a- K- e1 U
#define N 3            //数到3只时退出第三只
! U+ F9 y- R8 R6 T. B% Jtypedef struct monkey, x2 c& L% F' H
{int number;
" \9 W! r( f4 T; \( iint flag;
# X- e7 b9 {9 h; [# J; R  vstruct monkey* next;
  U: V) k% }% n9 q8 ?7 Z/ J9 S}MONKEY;& l7 N# }: @; s* f+ e" `0 d
main()
' W# R7 l& T/ ?& U% N$ Q9 ~{ MONKEY *head=NULL,*p,*s;
* T2 u+ `9 w. y5 Q$ P) A/ J  int i,sum=0,count=0;
  j5 @+ r4 D+ N  clrscr();              //清屏" C  b6 V9 P: d  k
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
% x. b: b. B4 T+ s+ o  p->number=1;p->flag=1;9 z+ N2 w* N8 g2 a
  p->next=head;0 J6 V+ g6 U$ X2 p2 }, c& c3 ~
  head=p;7 x8 ^$ G& o& ~; ?6 o, O) a
  for(i=2;i<=M;i++)
8 s; n+ a8 ?: V4 c5 @    { s=(MONKEY *)malloc(sizeof(MONKEY));
4 Z. ?% K/ @2 Q1 r5 T# w1 I     s->number=i;s->flag=1;
- v) Y( i2 l& K     s->next=head;$ w9 l5 a6 E7 W% X
     p->next=s;p=p->next;( i9 P' \. ]# k- \9 L- ^% l
    }/ J0 {- ?0 c+ m. @5 y& g
    p=head;
/ T' @0 \3 _! ]9 _, {$ E  A. x   for(;;)
# R8 ~! d) }+ ?* c% ?% Z$ w    {if(p->flag==1)5 {! R, v9 j5 L! h
       count++;
$ i0 A' ?& {) u5 J8 D; c* `     if(count==N)
7 U. ~& v" f5 k( }3 T/ a; ~        {p->flag=0;
3 J/ L, O0 p8 w+ u1 ]( j         count=0;
0 {1 j+ W; ~' D         sum++;}# d- _! C! J3 o
     if(sum==M-1)
0 g/ U# P( \+ J: O        break;3 }  N- W; I, I& q& y  }+ I* n: P1 O
     p=p->next;9 y  ~4 o7 W( \) W
    }( l2 N+ t# @9 I7 p; h% ?
    p=. t0 U( {; Q4 Z( |
    head;
: E  ?& m" I" u    for(i=1;i<=M;i++)
0 ?+ V- P! k) E5 h/ m# s$ I: f% {    { if(p->flag==1). X5 H" n9 E$ e( @
        printf("\t%d",p->number);2 v/ i4 G! u: M3 [  A4 T! d- h
      p=p->next;
# {: r% M3 D: r4 \/ h( D' d    }
' {$ s5 L& J2 _& S/ w+ x( Y5 G" {0 I6 O2 {& n5 ~

+ Y: @# c2 }# p+ n" \' o/ r+ ?9 y/ @1 {7 j- s7 L9 @  V; ?/ z
}
2 I! R8 {9 p/ @  r* F' F
第二种方法:数组
# Q2 A1 a/ e# Q! d# }) C4 B#include<stdio.h>
* c% J+ o& B, }+ H#define M 8
5 i  ~. g# \2 |1 o" W3 K  q7 @' F# `struct monkey% s5 _$ y/ `9 r4 p- l$ p8 |
{int number;( q) s% R+ W/ F& z, l
int nextp;
: @/ r2 |. ^# }3 C, v' {8 y: d}link[M+1];
  K4 r% v- S' G  k- q
3 z5 x" t7 h: {6 G3 f0 p( cvoid main()! f: m$ C* M8 A" p6 ^
{int i,count,h;
. `# |& c& H) t' W! `' u0 afor(i=1;i<=M;i++)3 X# m, d5 N. l) `6 p8 D* y5 h5 f  B. I
{  if(i==M)
. G. g) m* D* h" L   link[i].nextp=1;: m7 j0 o5 |1 F. A
   else1 K2 ]3 J( s# E8 T" F
   link[i].nextp=i+1;+ j& P% n. k  i- b2 [
  link[i].number=i;
8 n) t: o5 ~: o) L' k5 l}- w1 i2 a. }1 @4 T: [* P. n
printf("\n");9 Z5 I  ]  Y4 d- }. C
count=0;
: ^6 S3 Q+ J& x% K) @h=M;
) L; r/ ^  ?9 B9 G7 lprintf("依次退出的猴子: \n");) f% f; v% n: R3 S
while(count<M-1)
; q* h9 N( K4 [2 B$ e" G6 e{i=0;* _$ y# L6 q; ~( \- q
while(i!=3), M# q' [1 i/ t, i( l- D- W
{ h=link[h].nextp;8 k9 D* C6 W5 @& P( e: _# j
   if(link[h].number)4 W+ g9 z1 S1 K9 W
     i++;}
8 b6 H. B  h6 z" z. s5 f
8 ]0 K& U/ t2 C% ^printf("%4d",link[h].number);; R; j4 a1 J8 P) H- a' z9 G6 P" F
link[h].number=0;
/ A' `# I7 R; z+ r: x6 p) Y& \6 z* h3 jcount++;' Q3 s* t% H2 L: u6 S: f
}
' l  B5 R) [2 Y& p, o- p; ^: e* h0 x$ R3 ?2 a; U0 j% u
printf("\n大王是:");
2 F+ I8 A5 X) K$ L% J$ A  for(i=1;i<=M;i++)! [9 g$ a8 O' p& i+ i' L
  if(link[i].number)
4 A. R: O9 ?$ e    printf("%3d\n",link[i].number);& k- j, D/ V8 ~  ?8 S2 r) ^
2 L. y& r( x& D" l+ e! N
+ M0 E6 `1 k( V# n( }8 T
}
- q8 P4 O& \& X8 B2 w& C. _6 k( z
第三种是普通方法for循环
  y2 ~# ^, x) T; N0 s- c2 ]7 x
#include<stdio.h>
) t% q. u0 N0 Q  f1 g( |! U! ~void main()
1 ]  S+ T8 ^4 M! k8 ]& X7 ]{ int i,k,m,n,num[50],q,*p;! I8 W4 Y4 I7 j( Y* g
    clrscr();  b: q* N" t! A6 x+ J
   printf("input number of person: n=");
; ?5 T) m7 x8 C: t4 [4 P    scanf("%d",&n);
0 d! `# `. Q( j( e% m' {8 `printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只4 J+ B& U- m( e. L$ h# Q
    scanf("%d",&q);! o8 C. [4 q: M: E  m: M+ R  J, g9 x
   p=num;& y# K7 q3 j. {% j' |% R
  for(i=0;i<n;i++)
) m  D; e" {) [; t    *(p+i)=i+1;; }5 s- B  n& k' J: R% `5 E
   i=0;
* E- B6 C! C. v4 T9 y   k=0;
% z6 |+ G7 }6 N0 B6 K; f   m=0;, e& B2 j% V. u: v
  while(m<n-1)
+ h  U; g' [. W   {if(*(p+i)!=0) k++;. j$ E7 n$ |( N
     if(k==q)
3 j; D% G  L/ Z1 s" Q1 w: O0 |      { *(p+i)=0;
' m; f( L+ I2 Z6 k# O0 s& \        k=0;5 U# E' G$ u/ ^  X+ d& T- p6 b
        m++;* W. D$ M4 ?+ E6 t0 v4 f
      }7 T& I4 L1 M4 N. L$ D
    i++;
* _1 o5 R8 |8 w2 F  d    if(i==n)i=0;
  P7 s9 V0 @9 G- m   }
' X+ P) q# W/ N, K3 u" L; }  while(*p==0)p++;
! H; ?4 S5 e- {1 i( Z4 K    printf("The last one is NO:%d\n",*p);4 f: @# {" B- k: I/ R3 T
     getch();, G# r# D6 r# C" _

3 e/ V' ~* i1 m3 C8 k}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 q& O, `$ s) q" r+ V# X; ], j) e- Y
namespace 又费马达又费电
4 P1 f9 S) C9 O6 y; _7 o{
% D% [; r( f3 |% s$ ^. [- e    class Program$ K# ^& W# g' U5 x- l0 |
    {
$ I5 ?/ j. s# E/ V# i- i' z0 \; h        static void Main(string[] args)
, y# q2 z. m0 S6 g' ^. w4 k        {# x7 G" q: a) }+ d/ K6 w1 Z
            int m, n;
4 e3 f+ r( d0 U/ ~( ~5 W2 L& ?            Console.WriteLine("请输入数组长度");
+ h+ z" P& @3 l5 [' a' `5 f            m = int.Parse(Console.ReadLine());//m为数组的大小; o; g: C/ J& m! v
            Console.WriteLine("请输入要截取数字的大小");
: J7 Y. Z- t1 x* j& m, e2 c            n = int.Parse(Console.ReadLine());- V+ ?6 h- c/ Y9 B5 ]+ U) F7 E( {. L& d
            int [] numw=new int
7 |! b& V( f, n% U: k% N' [( Z. \) Y" O* k6 A: J
&shy;&shy;&shy;;* J0 M6 V/ D8 p: i' W! y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
$ q$ x6 Y/ E( X0 E6 Z            {- x; n, n+ }- e9 D
                numw[j - 1] = j;
# |2 {0 `! x+ X. R7 L- U            }6 V2 x8 Z6 h* y  r: Z& c" G
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
8 w6 X8 F5 K! v5 f) `            while (d != m - 1)
* T; d7 N, p9 ]1 G. P+ F5 g- y4 ~            {  _; ?* K; r: z8 ?
                if (i == m && d != m - 1)2 K) y5 }- \- r( W/ z
                {
8 p# |# c# Y! S2 @                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
. Y$ j, p  N7 ^) T                    continue;7 f* V, B6 k' W
                }9 E9 j& T& b: R. P) [1 x! X
                else
. @" T; {' \) T9 Z" w) K                {: T1 t! C+ Q4 O! S9 U
                    if (numw[i] != 0)
4 B" I8 f2 e  a2 C5 n* B                    {
+ _% \* K7 q# @2 S! a                        i++;: @* _' U3 u" \+ c3 g
                        k++;
1 i3 G- {; A! w$ O& n9 V+ e9 I                        if (k == n)
8 s( B" @0 h- _" s( Z' L  c                        {
9 l  k9 P6 ~1 Q: v5 {7 L9 ~, T, ^) f                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
5 M$ Q( D. p3 z                            k = 0;! H: b7 |) t3 H7 T
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小14 K# c+ _8 X( r
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
4 q; X( d4 n( |  D* x# H                        }
! Q5 m) _) a$ v- F) ~. a                        else//输出暂时还没有改变数组元素的值7 I: `! S) F. r- z' p
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
" y# T6 [3 w: C                    }
$ U4 k0 }$ T5 R: a% N, U4 V                    else5 I' j# M3 B3 s5 ?- W$ ]4 w7 ?
                        i++;//数组元素为0,直接跳过,不计数。。。
6 O/ S$ H, l' ]  h- r5 w0 O- ]                }/ R4 c9 y$ q( `* R. |: K

# f' P' i, d. w# H  K+ y+ [: f0 q, S4 B' m" e/ M3 _3 e4 c6 S; v
            }//结束while循环
7 b$ e4 o) K; Y9 j            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
" ]* F% ^7 `" k8 x" s+ @) {/ w           
9 B6 L; L4 Q9 X- l                if (numw[i] != 0)  `; }2 E% e2 v% b2 P5 d( {
                    Console.WriteLine(numw[i]);* J" z* L' _" D% W& L
           
: w3 H2 B  Y  s# A+ q7 Y            Console.ReadLine();
, ~, K! r. x0 [( W6 o8 U4 b  O; X5 b        }( x4 ?$ I* R! |# c
    }; y9 T" w) l5 E! E
}! E  D& |( c2 }7 [& A
小甲鱼最新课程 -> 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-7 23:36

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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