鱼C论坛

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

猴子问题

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

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

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

x
大家好!- ~& |# _4 ^" N9 o9 T3 K
这几天我在忙着编一个问题,我用了一种方法编出来!
8 P1 p: J$ {4 A但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!2 H9 |, |6 r+ v' E
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
) P% a% f) [' {: ~0 i" ?" l: X
/ Y/ z  l$ _& \% H4 P0 I( l  c! P. M. j* m
                            题目" n* K5 G' a  [2 ]- }4 i3 r
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。3 R( ~) S  k% E' w
第一种方法:利用循环链表4 \7 ^% w1 K9 I1 o
#include<stdio.h>0 U# F! T- u# C  Q
#include<malloc.h>8 a9 w1 R2 n' ?8 I- }) Y7 z
#define M 8            //共有8只猴子+ s# K6 p, r7 t& C8 ~, F; c
#define N 3            //数到3只时退出第三只! h6 L( t3 P7 ~
typedef struct monkey& o# u9 {( j( A& x3 e( l" t
{int number;
/ I" u" ^& v+ V  [. a9 R. |. V1 mint flag;) l+ n' Q  @* p  R3 v+ M
struct monkey* next;
5 Z' V3 r$ ?9 o: a  B# H$ l/ e& }}MONKEY;. S/ s9 }/ H' O$ }
main()4 m+ V/ H8 i! Y
{ MONKEY *head=NULL,*p,*s;
' E8 C3 U# j! s, ~# M* }: X* `  int i,sum=0,count=0;" P, U& S( K' i+ p' F
  clrscr();              //清屏
; X  x7 T0 o1 L3 O6 D' p7 M# E  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存- x, c3 {% k. {& E
  p->number=1;p->flag=1;
4 j  s; C, B# m3 }  p->next=head;
! g5 d2 y6 T3 Y, L! k+ N$ F# @  head=p;
2 `" Z/ U# j! R9 X3 m) X3 k  for(i=2;i<=M;i++)
6 R; [5 G  d9 j; D3 Q% r    { s=(MONKEY *)malloc(sizeof(MONKEY));' I  i% G. J8 B& J
     s->number=i;s->flag=1;+ E" T' V5 h1 \4 U
     s->next=head;2 ^, f& S/ F' d7 u; d
     p->next=s;p=p->next;
1 _- D  r7 p3 X    }
* O. n& H1 T8 q, A' Q8 o& r8 P+ S    p=head;2 k7 v0 j4 K/ I6 a! {
   for(;;)
. }" g. ~" f$ w    {if(p->flag==1)$ ^# |2 N  A. X, ~+ |5 R) |+ }
       count++;
* ]! p" |4 {" G( _' \     if(count==N)
7 q) i2 U' K: L- B5 \        {p->flag=0;
3 H9 `, a2 V/ F( t2 K0 }0 N         count=0;7 u9 @* ^  d% A6 J
         sum++;}. ]3 t- C% K! L5 ~( U/ k6 z
     if(sum==M-1): s$ L) F' g6 S! q, s, }
        break;2 l+ b" E7 R0 m, R  ~
     p=p->next;, M6 k8 `) M3 Y8 \3 g( C
    }
7 C% L4 U" p% h0 E8 e    p=
) \3 f& v3 \5 R7 e, p2 @# h    head;/ m) z7 J2 P  L
    for(i=1;i<=M;i++)
6 ]; E* k* I: N, R    { if(p->flag==1)9 K. e3 C7 i/ A/ k! u4 v- l2 e
        printf("\t%d",p->number);' m6 x1 }4 A1 x, d
      p=p->next;) O( _/ `! b, k; }1 |
    }
" ~9 S: m1 w+ T8 d: j) T, h; d! j- i
/ S& i- T! E8 {& K8 j

- F, t. r" Y5 U}

* O5 O8 s- v" }8 N第二种方法:数组
/ z$ E6 l: l. y& N! D#include<stdio.h>
4 k, l6 F+ G; ], ?#define M 82 W+ Z% \; h, K" a9 x
struct monkey2 Q2 P2 S) p+ L3 v
{int number;, C, r% W) M7 C/ N( L0 z
int nextp;8 L/ J+ O; G0 g0 E- f' y& L* \
}link[M+1];& R' Z! D4 m1 h! G9 u! E3 U

+ m& C3 k6 i: ~. ovoid main()$ |' n' G. L2 O- O% r
{int i,count,h;0 F7 i$ s3 U7 P  m; x
for(i=1;i<=M;i++)
8 D. k- w' C, s- v: x( i{  if(i==M)
; c" o" }0 O; ?   link[i].nextp=1;
( i- H* l2 r1 X' G' L; q   else
# C) X7 ^! p- [: {   link[i].nextp=i+1;  K8 r  d8 E( S+ {& _. a
  link[i].number=i;
1 ~4 |) @# i# X% ~}5 h5 v2 X. A+ v# L1 ~$ ~/ t! R
printf("\n");9 o  A' ^% \3 F3 m. @% g1 k
count=0;
: A0 L  p) V+ D5 bh=M;; f0 n3 |. P% G% V% e- U" u1 r
printf("依次退出的猴子: \n");. f' ~1 n0 D+ E& I: l: N
while(count<M-1)
7 u1 q& _! N2 y% i{i=0;, C8 V( X# {* c- F
while(i!=3)/ i  L& B3 ^  k( ^1 e
{ h=link[h].nextp;
! D: x8 f5 l3 m1 i0 a2 D   if(link[h].number)0 r8 A9 f/ y6 K. b  T
     i++;}
, n- t" `' }" P; N. v
2 V7 G6 R  @6 Y# v/ p5 Bprintf("%4d",link[h].number);* D5 h9 W1 t3 d' B
link[h].number=0;8 F, S# q/ i1 [/ Z9 N1 x! E
count++;- t# T7 r1 a3 r  Y: f% Q- Y8 [2 u
}
7 `# U" H: z: e  b
5 F) l9 I! F3 \+ m3 @printf("\n大王是:");6 N2 d, z% K) N9 b
  for(i=1;i<=M;i++)
0 U  j. T  ^- ]6 B  if(link[i].number)
' M9 V, G% }: c2 j- e& b$ P+ o    printf("%3d\n",link[i].number);
! G6 p% W% v1 E6 S: Q9 F
5 n7 F* u$ k, I+ u
4 }: @: B9 v! I3 z- M}

/ _8 I& e7 M+ n+ ~第三种是普通方法for循环

, ^% H" K" R, Y! [" `  S, Z4 m' A4 m#include<stdio.h>( u5 r  T$ a* {* N# [  }
void main()
" a5 K, K; f  u8 p4 s. r{ int i,k,m,n,num[50],q,*p;8 e, o4 R! t" G6 _, t5 |
    clrscr();
, l# |1 D# k- ~/ A" x/ B4 L   printf("input number of person: n=");
& P& `2 v8 u# P( I2 {    scanf("%d",&n);
  A5 [9 N3 b- |9 L7 R0 vprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
$ X1 Y+ W$ z0 R0 v; o2 j1 B    scanf("%d",&q);
5 |# y9 r4 L/ W: t$ N# k   p=num;
! ^/ u8 [5 X# c  for(i=0;i<n;i++)
4 D, g4 S7 p# O8 G    *(p+i)=i+1;) [& @" Y0 L, i. w
   i=0;
( V7 Z, \7 W/ W* G' @. D4 i% g   k=0;; d3 [" x* F: ]! q0 g# @
   m=0;9 Y! h6 P1 D, d9 f
  while(m<n-1)
4 w. a2 U2 V* d! N: @; A   {if(*(p+i)!=0) k++;9 `& l+ e  ^0 G4 \- p
     if(k==q)9 ]: s4 i. r9 K! b, g
      { *(p+i)=0;
- M. R0 O3 S6 j# k" A4 B3 h        k=0;
" W3 @+ G. t3 \6 P* h        m++;
- j( C$ M' h; k) ]& A0 b      }: J9 V0 b: H/ L  u& q% y5 N1 i
    i++;) O+ Z5 s, G- }3 [/ o! Y1 Y
    if(i==n)i=0;+ Y: M) A, X2 j' C; c) E
   }1 |; i1 X' }" W$ ?
  while(*p==0)p++;0 M5 X" K3 C: s2 ]  t/ o
    printf("The last one is NO:%d\n",*p);- W7 h, o1 v. V2 a
     getch();. H+ c  H# d6 D! T
  ?9 B$ A+ B, {( h8 D" J: P' k% C
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
; F4 U6 n* S# r" z3 Inamespace 又费马达又费电
" E$ D, x1 _: e! H, z0 }9 ^8 |{& W4 O$ U9 H( c( T, {6 H/ |9 q
    class Program
2 ~( p3 q/ g. o6 o    {
; Q% D: F9 x1 S5 _/ j4 s6 {        static void Main(string[] args); u3 G6 q! l3 Q4 R
        {
: Q; O0 U+ ?  m( q1 l) O* [            int m, n;
9 V. o1 O8 _" O- v* k/ l8 o6 f" y* `            Console.WriteLine("请输入数组长度");+ O0 e% _0 P" D) v0 g) |
            m = int.Parse(Console.ReadLine());//m为数组的大小9 Q7 J8 {6 \' r
            Console.WriteLine("请输入要截取数字的大小");
( q4 o+ K7 N( o1 u! ]            n = int.Parse(Console.ReadLine());
2 g, }: C+ Q: c, [* ]" x7 e& v            int [] numw=new int0 b! e) A' D5 v" n- c6 x! x

  v2 Q' K9 [- m1 G( T7 o9 E&shy;&shy;&shy;;
/ G; ?6 x" M' u0 ~            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
# f# u8 X% D8 f; |9 M% U            {
* X8 |3 ^1 v& ?, Q9 E                numw[j - 1] = j;
6 B+ r/ s2 k9 |            }
0 ?9 b- N: e0 l+ O, [  u- X            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
4 M& p8 ?5 h* z' a) }            while (d != m - 1)+ z* n+ `3 r1 I0 p8 g  o
            {
/ J  ?3 t# Y2 M6 }" G                if (i == m && d != m - 1)
% u# {; G: v; s' g0 T1 r                {
4 f2 @. A* H' Y0 O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!% c$ ^1 a7 K0 M1 U
                    continue;) V$ Z8 x- t( j6 ^, U: Y4 _
                }  i; ~  M" |2 o  N4 e: q1 E% g
                else
6 Z# E9 }/ `& _: b# V' [- x# D                {& u  D6 C; c, ~- u" m
                    if (numw[i] != 0)  J. O, R/ w9 N) X4 s
                    {
- e( F* V% Q) H' C                        i++;5 t) d: c4 p% y5 H/ I# W" O1 _
                        k++;! l0 @- m$ _: Q8 n
                        if (k == n)( q4 E# Y% Q5 D* y# ~2 x
                        {0 S7 I/ O0 H7 L0 G
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& ]: I- N6 y9 ]5 t7 ~5 H5 C5 i
                            k = 0;$ h# }  o3 l* S: Z) n$ j. F1 z
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 w5 x4 w- \4 c& |3 h& i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);1 S2 Z7 j) u9 `1 L8 Z* }* F- I$ t
                        }
$ L' U& F% w: D" ]4 z8 |6 K' V/ H                        else//输出暂时还没有改变数组元素的值! x  l4 p# a! I. K3 Q
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, M, Q% l8 \2 f- J, _                    }7 s! S) h( w$ X& l* o6 S+ H
                    else2 S( I* d% L) o# y1 q+ D1 z
                        i++;//数组元素为0,直接跳过,不计数。。。
! e# I0 T5 K' _" b7 \7 x& Y                }
+ S9 \! r' g! [) Y
5 x! e% i" f  `# I+ x7 U% H- ^- ]  D3 |3 [
            }//结束while循环% _5 B8 Q% n) [
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦- O9 ^2 u$ c! h7 q) ^1 N. u
           
  D. L- Q) L/ V' g2 A# a0 b                if (numw[i] != 0)
8 ]1 C. G! p2 B1 n! ^/ H                    Console.WriteLine(numw[i]);8 g) y# Y9 G2 f2 [5 [& j" g
           ! o: K6 s$ k0 X' A, M2 B3 S9 B
            Console.ReadLine();
9 z7 r4 o. Q+ m2 Z& U( N        }1 i. `: D" \; H5 s2 b
    }
& G6 n$ Z' f# N* d* f4 v}
5 Z* q/ q" K& ^3 ]4 v
小甲鱼最新课程 -> 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-18 04:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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