鱼C论坛

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

猴子问题

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

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

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

x
大家好!
$ G# t! O* q2 _# H; b这几天我在忙着编一个问题,我用了一种方法编出来!: m# H# I/ ]8 R
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!1 F, {& H, s9 V# `* s0 J
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ) g! S, B) H" K8 [

7 z' M- Z, }4 t2 a) U  [1 k$ T6 @
                            题目9 S7 o* @$ t& J' C# z  K
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。4 K+ k; X, N% ]) f6 _' \- D
第一种方法:利用循环链表
' U7 E9 V8 t- z& ?; V#include<stdio.h>
; _) j+ P9 ]" B1 w0 y#include<malloc.h>. c- H- E" t& K' n4 t* Q4 Y9 t  d
#define M 8            //共有8只猴子
7 j- z. X& l1 }5 M/ n2 k#define N 3            //数到3只时退出第三只" P& a. q% V' C9 }* g& j: U' ?
typedef struct monkey" ~9 M) A' F4 s, t6 P" m$ G( @
{int number;
1 V, B2 W' c, g0 }int flag;
- D/ Z7 y, l# f( _' qstruct monkey* next;6 P+ {" Q) N+ Q# ]5 o
}MONKEY;+ x% `- E- W! }1 s4 f
main()
0 V0 j. Q) F: p{ MONKEY *head=NULL,*p,*s;
1 c) N/ _- f+ g8 ^% ]  int i,sum=0,count=0;! h/ S# N  U+ a$ ?9 y6 ^
  clrscr();              //清屏' I' S7 l% o% {+ E! V! p0 O
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
4 \7 c" x% Y7 b: T( l9 J2 T1 u0 d8 {  p->number=1;p->flag=1;& v! ?& _9 M, m9 g( M/ o* E5 m
  p->next=head;
/ D9 _4 G) l/ y) _& ~! @, p  head=p;
, F  S+ e) L4 r/ d  for(i=2;i<=M;i++)7 M6 u/ W! f4 f# ], _' v
    { s=(MONKEY *)malloc(sizeof(MONKEY));" }( g0 @" z/ H# I9 {+ w4 y4 R8 }
     s->number=i;s->flag=1;7 y6 q' z$ U9 ?5 c
     s->next=head;) ]7 n9 v0 S) A  V! [. r
     p->next=s;p=p->next;& i" c" @3 J% q) v7 E: r8 `
    }# W1 i' @! E0 d! x; v
    p=head;
% ]2 r3 M; W/ Y( {- T1 [5 r   for(;;)& x# U5 N  m: h5 O
    {if(p->flag==1)
$ t: m% \8 o, z: y       count++;
6 V  k7 a. D6 n. I  D  \/ m3 k6 r' ~$ b     if(count==N)( T7 s- _. H( g7 n+ d0 X
        {p->flag=0;$ l' ]* O. L+ P& C
         count=0;
. ?! a: Z) s+ h- g' T         sum++;}( W/ t* m& M1 E: a" E
     if(sum==M-1)
  G5 s: s" z) L2 N% Z! O        break;* J9 v5 ]6 i  M! ~+ `" ]
     p=p->next;1 n5 z% M: R4 f9 f( l* R
    }
1 H" a% f' `$ t! S! g    p=. O2 d" P# O: t
    head;
' @  Z4 _* t% u  b$ V3 h! f3 R8 e- Y% u    for(i=1;i<=M;i++)
6 c4 q& s. c' r: m" m7 X) d% N    { if(p->flag==1)! A5 P  q' G2 E0 c1 N, I1 p
        printf("\t%d",p->number);
9 \2 J5 h" r7 q; `7 B/ k- x      p=p->next;
$ ?3 x$ `& m6 P    }
, M4 k4 Y+ D; E$ l7 c& O' E% u- R/ e' U6 k

1 p3 A) I: b  n, L& B4 p8 O: S% @8 F7 e' e3 z
}

6 o2 n7 X3 @' b% V$ v+ T第二种方法:数组4 p' x/ `3 {' i  q! \8 C1 e
#include<stdio.h>, W" O+ F4 a: B+ _4 R0 S
#define M 8  Z4 h; ]1 E/ T/ \
struct monkey" @6 B/ I8 ]9 e2 Q$ J! s
{int number;. X. Q- _3 R& N. m* ]
int nextp;
4 s# d' q! p' b7 B: I( Y- {}link[M+1];- b; G. E/ \8 L' v: ]7 c

' N% S$ ]# T3 g9 u! d7 l% a+ Y0 B  Lvoid main()6 |  ~% z3 n  O+ |: x6 Y2 q1 C
{int i,count,h;
, Q4 P6 M; M- L, u4 _for(i=1;i<=M;i++)7 X5 h2 f; N0 Y# R4 w# R0 G
{  if(i==M)4 V# @' ^% H" l+ X: T; R
   link[i].nextp=1;
  o% P) y5 o0 ]1 P' P# G2 L5 e   else
7 G0 Z& [9 y1 [" G. M3 b   link[i].nextp=i+1;
3 u8 p% x3 m' z  link[i].number=i;
% B4 a& @: w; n: l* l" a. E5 A}& h5 l  r& _/ i
printf("\n");1 Q/ F9 X- {% \/ o* e. R
count=0;
) C  ?; `0 H* a# x2 sh=M;
0 a" x: I1 a$ y5 G: |) }  Cprintf("依次退出的猴子: \n");% n3 [. L* G1 e0 n2 l3 S% Z9 r
while(count<M-1)
0 M6 n  _; [+ q  t5 N; Z) D{i=0;; q! B2 L1 P. @9 ?6 T
while(i!=3)1 E! m$ _9 V* l" I
{ h=link[h].nextp;
# m5 l" i4 b- r! l9 }" u# I% b   if(link[h].number)
( T# ?- z" b$ l$ a2 e# i! B4 [     i++;}
5 L# c! b- A7 x1 H) J0 w
  C+ T) A: T/ L6 k* kprintf("%4d",link[h].number);6 R5 y% ]$ {( v; Q0 p" U
link[h].number=0;4 r( g1 b' C" H9 V" q
count++;# g- H0 ?: w( a3 n: M
}. u  B% @7 d2 |6 m9 v8 A
! b. q: @# L8 U) z# E7 |  v
printf("\n大王是:");3 g. \& y# M  r$ m& K' ?
  for(i=1;i<=M;i++)6 y* [! t- W* ]) M
  if(link[i].number)2 B; I3 U8 E5 _+ b
    printf("%3d\n",link[i].number);' M! e  T9 s" v1 F: L: B" W
; a9 w6 F. f6 U0 z$ c7 m
4 f, I6 B( Q0 x! n0 r
}
1 G+ a+ V8 S0 \+ X) a
第三种是普通方法for循环
! Q+ x- L8 @$ h/ h
#include<stdio.h>
0 f2 E9 [5 S, @void main()
% N! ~6 m9 N% {1 v/ d6 `{ int i,k,m,n,num[50],q,*p;
$ ~2 Z4 q4 F  b4 l3 @0 }    clrscr();
7 s- i; \5 |0 I! `3 q$ Q) o! E' H% C   printf("input number of person: n=");/ b; Q! c7 x; j  ^
    scanf("%d",&n);$ t5 l+ _" G! w/ }- Q% Y/ @
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' S: F  ?. k9 `7 z: @    scanf("%d",&q);
- }* `5 ]( S) O4 N4 O   p=num;
1 _( D$ ?; H# D2 B' T; ^, s  for(i=0;i<n;i++), l8 [1 y1 @  G
    *(p+i)=i+1;
& p4 q+ |! }& T- u% \   i=0;
1 {6 ?# N' c2 i! `0 w# E   k=0;
' \$ c/ g6 ~0 c" E; D5 m9 j4 T6 |   m=0;
4 s* H: W+ U  n: @: o: X; c  while(m<n-1)
! F1 y3 D7 L' D; E   {if(*(p+i)!=0) k++;
0 N/ v  p: X4 l3 _( d3 o7 R0 T     if(k==q)
2 k2 b) i9 W5 ]/ w3 _4 N: m/ F9 s      { *(p+i)=0;
( R6 Q& z) w. X% V, P        k=0;5 r# @. }$ {- u
        m++;9 k" S( Q; F! ?+ C2 X
      }1 O: H+ g3 A" X
    i++;
3 |& I6 Z% I" ~6 @2 T' i% R% _- p    if(i==n)i=0;
+ j  N) k+ W) S3 _0 N3 O   }* q. E6 O  e/ D+ q  S, l
  while(*p==0)p++;
7 k5 k& K+ ^  I% J/ z, X7 S    printf("The last one is NO:%d\n",*p);& H5 \" }8 M7 Y: t
     getch();- R3 C; X1 n) _; c; {

/ H8 z+ h6 ]  Y, `1 F# T0 b}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
5 I7 f( e' K0 ]" |namespace 又费马达又费电
+ v, K6 X6 \: j8 H9 [{4 \" x7 c  N# a$ E3 [# {
    class Program; a3 t; y) B  l8 T9 l) u! v( t% a
    {
" Z+ i' z4 M( S! Z- a        static void Main(string[] args)* y, o) t, A& c$ R4 o4 g. s
        {
, z/ Q1 M6 X( j, V* q9 g. b            int m, n;: J4 N' W3 k5 J; a6 l. y
            Console.WriteLine("请输入数组长度");" m. k! y5 W# ~+ Y# V& X
            m = int.Parse(Console.ReadLine());//m为数组的大小
$ w- K4 T- A9 B' R' B            Console.WriteLine("请输入要截取数字的大小");
( K, L! d# C5 J9 T! m2 W& O            n = int.Parse(Console.ReadLine());& D8 ^- F# ~! z2 i/ S( h
            int [] numw=new int6 s, I, W: h: [, p) g7 d
7 d% A: i- f' F1 X6 V% P3 b* ?9 F) X" l
&shy;&shy;&shy;;
' C" q% q* N  r0 u0 [, I" a            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数6 y; z" k  a5 `, G  e' n4 o/ |
            {
4 f4 `1 L& [& d7 ?: P5 ?                numw[j - 1] = j;
* w3 {. _% T8 N7 X5 h6 u4 k            }
. N4 @6 o$ Y" }            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. c7 e& |9 T8 o; J# s            while (d != m - 1)
" E3 l7 i0 m$ G; I            {
3 ~5 x$ O4 A$ r2 @                if (i == m && d != m - 1)7 e  C5 @! W7 Z+ G# U2 g. x( @
                {. R+ e* U! H9 n1 \+ [0 W3 {! n' Y
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!; M9 p) ~- g% A8 R0 X% Y3 Q
                    continue;
2 ]0 O% \# k3 @7 S4 G/ K                }
7 r  [- E, b' O8 n* P, m* x6 _3 X# U                else
/ I, ~* f4 I  J2 e# P                {0 R9 V$ b& o9 }* A
                    if (numw[i] != 0)% O% y% I: S* e: m1 r; p# g4 k
                    {% I4 i8 L! h9 J. e2 S1 I
                        i++;
8 A" K$ O. t* }. X' G$ P4 `                        k++;
4 }# `* t! C. |                        if (k == n)
$ F2 P" p4 X" ]. {) @. F                        {
4 U* n; P3 c: k1 s; q$ Z1 h. m! P                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
. \. `5 j& u0 E& i                            k = 0;/ [' Z; E9 U4 p/ J8 D3 q- o
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
$ {8 z5 F# k0 r                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, N* j1 X! A% @$ s( J                        }" N3 {) I. C# L/ X+ ?( K. ^
                        else//输出暂时还没有改变数组元素的值
9 W- k1 K, \3 ^# {                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);% r. Z* @6 G! z
                    }! ?) x2 p; i. \- V; q
                    else
0 h9 F- X# R7 Q0 ~                        i++;//数组元素为0,直接跳过,不计数。。。
; q+ {, \+ e* j0 m. Q; i                }
  b" {6 g6 u$ } 5 }& G& j3 E$ _: w

; u2 W* E# b7 v' L            }//结束while循环* i, L9 h5 K! `9 H
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦. y' S+ Z7 z6 d* t2 i  ^
           
% D' s* h! [- \) H2 {, Q% E' G, X& f                if (numw[i] != 0), R, ~8 m/ H: G: T
                    Console.WriteLine(numw[i]);; ]# q0 U8 ]& l6 S3 W8 [8 b0 c
           
# H- c7 Y( l+ Z. |            Console.ReadLine();2 m/ B+ Z7 D8 ^# a! l
        }- N+ ^' H0 l7 G9 j. ?
    }: x2 K' H4 \+ U8 w. N4 F3 W
}2 f, Z7 }! e$ c; a0 |# c
小甲鱼最新课程 -> 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-7-9 04:18

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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