鱼C论坛

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

猴子问题

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

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

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

x
大家好!! f6 q4 ]+ x& J1 k( G3 P
这几天我在忙着编一个问题,我用了一种方法编出来!
5 e0 X$ s; [! x4 l3 ?2 }8 D6 a但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!/ ~7 y; t  z0 s9 Y0 r+ A& ], |
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ! w3 `( n( h' x/ t
8 H4 L; q7 }) G9 G# z- h+ r6 G' G
$ D% o2 Q  J! N4 Z, F
                            题目$ U4 v3 S$ P. d5 h# L4 R& z& d
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
  H5 C" p( x. G" }6 w" |第一种方法:利用循环链表
8 z- x5 c+ s$ T, h2 Z3 O# C#include<stdio.h>2 o" c" Q& ], g+ |$ b' V9 ]
#include<malloc.h>1 i: X. g( v; b  }; i+ V+ P
#define M 8            //共有8只猴子& _1 I$ c' E9 z- U* [
#define N 3            //数到3只时退出第三只* d1 ^5 a# ^3 a: h3 l
typedef struct monkey
4 L$ y) t: E; u+ O$ s0 W4 B{int number;* d7 d* Q" p" U. v) j. p
int flag;
. x5 w. P4 A0 N8 u" bstruct monkey* next;
2 h7 P, {1 J& O% ^9 F}MONKEY;
: G1 v5 h- ~5 R' Emain(): u( S1 D: z" q' U0 T
{ MONKEY *head=NULL,*p,*s;
5 `+ F" c; q2 v8 i2 C" W  y  int i,sum=0,count=0;+ _2 x+ a. s+ E8 N' w; u6 Z; K4 J# B
  clrscr();              //清屏
: y. y# Y4 U# c- {; ^- \. m  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存3 B6 R- m6 g% d3 \" q$ M
  p->number=1;p->flag=1;0 G( K0 r. f, b& a  U( o" b
  p->next=head;- q. A0 U0 A" k; U6 s
  head=p;9 ~- a2 e  d4 z& I% M- {/ f
  for(i=2;i<=M;i++)
5 F$ B* f) f9 G6 v3 ~9 N    { s=(MONKEY *)malloc(sizeof(MONKEY));
0 p5 t8 \' O) {" R) ?5 U: _     s->number=i;s->flag=1;
9 S6 J$ B- {# |/ m     s->next=head;  |) T. B5 R2 D
     p->next=s;p=p->next;; E- M- [7 A# [. g' ]
    }
) h+ W$ F# l+ E' v    p=head;) i- D; q2 c! _- ^6 s% W! v3 _6 i
   for(;;)) {, N! H$ r% [: B* k# o" f8 a
    {if(p->flag==1): i1 R$ ~& A1 S3 u0 g
       count++;& p; f. m) I& u; T; d, R" p; l7 y
     if(count==N)- x+ Y' W  k( R) j& W4 W; f
        {p->flag=0;# U. J! v5 ~/ `9 Q! X( t
         count=0;
3 s. s% T, `. x' d2 J  p  ^: f4 s         sum++;}! {/ e  K2 n& t% |6 \" j; f! Y
     if(sum==M-1)/ G) O; L  w, s. D" {
        break;
9 l( o  k$ r8 ~( s- r) _; C     p=p->next;4 F# q, S3 R6 i; R
    }
( e; f( O* f- C" ~  x    p=
' z9 G/ H, N( i" W* J8 B0 i    head;
0 i# v  C9 S& q* M    for(i=1;i<=M;i++)
2 I3 y3 G5 {3 E1 m1 Y+ l7 c    { if(p->flag==1)
4 g' W0 W& |0 a        printf("\t%d",p->number);
6 N; y2 I$ _% x      p=p->next;
' S& `0 c8 L  Z) Z    }) y$ h+ @1 q7 F. d: R; D) `1 r5 Q0 S

$ d2 M$ h6 P$ U/ T5 V6 [$ v* Y7 P9 G3 Q0 _5 O4 }: ]  T0 G' ~
+ {! \# Q+ x/ R: R
}
7 b* S. W( ^$ k+ `( W
第二种方法:数组
# A; q# S8 l+ ~7 N#include<stdio.h>
  ?. n: w/ b# ^" S1 d$ s, L#define M 8
% D- K5 F8 F3 p* [struct monkey
% D/ b- r' d( [- G8 S5 Y# \{int number;3 [8 y5 A8 r& D7 Y) s: w, j. I
int nextp;
0 y) r0 ]% B3 g" M' U5 t}link[M+1];
# F& l' S, @$ O( ]. x: w$ y2 K2 N! g: g7 D7 m$ m( s5 {
void main()
5 j  C( Z9 s& q. t" }{int i,count,h;; z$ j3 }" V$ F# q1 c
for(i=1;i<=M;i++)4 c1 M1 A* h6 ]9 A% ?7 a( x& ]
{  if(i==M)
. }( H0 c: O/ U2 j7 I5 G0 @) N   link[i].nextp=1;
% c, F7 f- W, _1 I8 w2 j   else% f- [# i+ n: m$ Z5 q" U
   link[i].nextp=i+1;
. O' |& d1 `# z0 M& ]- L  link[i].number=i;
# D0 G% _. i: W/ b# L* t# _  J}0 m$ x: @6 r, P  @( v6 g
printf("\n");  ^8 C/ c8 r: }, \  d7 L
count=0;
8 \, w5 s5 i3 ?; j0 e8 Gh=M;$ M% D& x2 V5 b; v2 h0 T
printf("依次退出的猴子: \n");% L! W$ v% A1 X" n+ p
while(count<M-1)# V( \& H; F4 s0 y% G( T8 l
{i=0;
" s, J- _) {; y, U# I. S7 }0 D) @while(i!=3)
  \3 f4 h( i% c. e1 V. A$ |{ h=link[h].nextp;/ b6 P  q& |! f- \8 d* H
   if(link[h].number)" @6 `& A: s. ]# b  L
     i++;}, t& k1 Y" d! j4 B* S9 n9 E) h
1 Z7 E9 \6 i2 k( M' n, X2 l2 ?: V
printf("%4d",link[h].number);* Y1 U) Q# t) ]; P9 {+ C- U
link[h].number=0;- P2 b  j$ u/ }7 o/ u# {  K$ w
count++;
' W- E+ ^) P5 k5 J" g}$ m4 }1 p: a5 v% T4 r
5 D2 M8 v# {3 H
printf("\n大王是:");
( ?) A1 D" e: z: X- ?$ r& P  for(i=1;i<=M;i++)4 Z# p7 N4 G( O2 D9 A! X% L8 ?
  if(link[i].number); `& e3 e" ~. K7 k5 h, I  @
    printf("%3d\n",link[i].number);
# u* J  x  W0 h( C2 C+ @& b# V4 h, F' c- T% h8 `5 [  J

$ N& ], G9 g) G% j2 l# R}
9 {1 X) [9 T: Q& l, A+ @
第三种是普通方法for循环

0 A; E0 ]$ e; z) ~" z. \#include<stdio.h>
' v3 `6 r# \- a2 w% m, t$ _void main()
1 ~' N  F5 M, B# z3 e* w. I{ int i,k,m,n,num[50],q,*p;! F7 S7 Z. r$ ~
    clrscr();7 O! I  D4 o, @& a
   printf("input number of person: n=");1 J9 p# P- h4 _. P' `6 v! Y
    scanf("%d",&n);$ d" A; F- z( ~7 j
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
) Y6 m9 e* Z3 R4 C: A0 H* n    scanf("%d",&q);
% s; N9 I0 \4 ~  u  V   p=num;& P9 S# q: g* O/ \; j
  for(i=0;i<n;i++)
7 t; r$ r. p' C5 C9 p6 ?    *(p+i)=i+1;
5 n' t) i5 ?% y   i=0;
$ D6 j3 C8 ~) j   k=0;
# `' ^" C0 }; q* t   m=0;" ^4 W# {0 `! b
  while(m<n-1)9 v1 f7 p. g3 {8 f
   {if(*(p+i)!=0) k++;) I. x& K. H5 w" P  A0 Z: c
     if(k==q)7 Q+ ^6 [% Y, U4 \
      { *(p+i)=0;5 ?7 R0 d2 P8 z/ x2 g
        k=0;
' q- U  a6 Z% Q' x2 q        m++;* }( b8 P- t, Z% o% [' R
      }
  {7 x" G. ~5 m/ H0 [$ K    i++;6 m1 q0 Q+ W5 H/ ^+ D8 C+ q( S* c
    if(i==n)i=0;
' L- b$ w# `  z) f   }. }/ k6 w3 n8 h  N6 A; l
  while(*p==0)p++;$ R: I% F$ T( g3 j
    printf("The last one is NO:%d\n",*p);
4 W' B7 m8 s1 g4 c% R     getch();
( o3 x" K/ j2 |: ], y& d8 h& Y' c: A5 v" X) _) R% o) M
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
' X  \( A4 R! V! I0 _: o% C- vnamespace 又费马达又费电! ~: s5 H2 r# M; F6 d8 a/ O- \
{
" `. [. ?' U) _+ _# N) z    class Program! ^7 K8 E+ Y  r1 E, @9 I: f& ^
    {  F5 Y1 k6 D) d# d1 C
        static void Main(string[] args)( V. ]4 ~6 Q# @- D. ~. M7 P
        {
4 t" ^9 q  i* ~            int m, n;0 {) n6 @. ?% s, C# y3 L# Z
            Console.WriteLine("请输入数组长度");
% r6 Q2 m$ z% Q( Z: L            m = int.Parse(Console.ReadLine());//m为数组的大小
8 ^0 d- K$ W: D5 M) X+ y4 t0 J            Console.WriteLine("请输入要截取数字的大小");  ^4 p' B* ]: A7 X1 Z
            n = int.Parse(Console.ReadLine());# P5 J6 p3 D- o% Y
            int [] numw=new int8 ]- }4 f" V6 r+ u5 Q- k& `' g5 {
0 a) h4 u) m4 G# J
&shy;&shy;&shy;;
5 O* [: S+ C& _8 R            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数4 [* R2 w$ O+ Y- T8 o: M8 t
            {
9 b2 m! R! f4 o# i1 u! W4 N! {5 g                numw[j - 1] = j;3 A: ~8 E; B# Q$ z
            }
9 A# Q% h1 O$ ^# v            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!: a) y" ?( p/ V7 Y' U
            while (d != m - 1)
. E' G; n2 J0 Y9 A* c! P            {
. p+ O, n! \5 j                if (i == m && d != m - 1)' L; D8 q* C* o6 R% F
                {
. m$ B! N  j' P" g, |* _6 a" |                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
( ]0 V6 y' C& c& v9 U                    continue;. m+ g' M  [& ]9 s; O1 O
                }
9 Q+ f6 ~% d! q/ A$ K1 O0 n: D( Z                else
2 O; M2 J1 ~4 S( f8 u9 z$ R                {+ R2 F4 O& @4 l& ^7 u6 ~; X' H  u
                    if (numw[i] != 0)* ^; A! z7 \& L/ G6 i# @& e5 @, ~8 t
                    {
" c% t0 o% [- R* |* p6 [) X+ \                        i++;8 K+ B1 F( X/ Z' C0 z! C5 w
                        k++;
2 I+ ]9 T( N9 j) O  t# G                        if (k == n); k9 c/ b  i1 y
                        {. c% u9 Y8 z' o! I8 m$ U
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 _# O- H* a4 `
                            k = 0;8 T- A; T. M& |# u
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1" {0 @" P3 P% ~- R% B+ Z, D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);+ p% [9 H0 u- c5 {
                        }
; F- h2 D0 `! t: d                        else//输出暂时还没有改变数组元素的值
- c3 j) \9 e5 v                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 `0 r8 t1 j9 q" j% \                    }
9 v2 H" ?7 \  f! t: W                    else
1 v9 M& [  D6 ~, h. c                        i++;//数组元素为0,直接跳过,不计数。。。
% M  d8 V' u3 _. {1 z$ o                }
: `6 M! y2 [$ X3 b, C! C$ Q 1 x% [0 P' J. A4 {/ H8 r: w$ l
6 x% x( h4 b- l* ?$ B9 ~0 U; y
            }//结束while循环
1 j( u2 X  F1 c9 D; g            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦7 g- q+ z6 d  f" H& B  i: k1 P
           ' o, |" p* `6 O% g
                if (numw[i] != 0)% v  D. x* t  ~6 O6 d! u6 H
                    Console.WriteLine(numw[i]);
+ E* W& _2 ^" z           
- Q3 D3 F; C! W2 m" E, b1 X            Console.ReadLine();
# Q$ c5 @7 t7 T        }5 j" x1 J$ J" p
    }8 P! |" Y1 L8 b) ]% l! U
}' F# @, i" [, A7 T6 s* ^! U- y) h* g
小甲鱼最新课程 -> 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-9 11:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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