鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 M+ L0 H# b/ t/ Z% E这几天我在忙着编一个问题,我用了一种方法编出来!
1 B! S( V& C9 E5 i* E但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
& A( u/ Z3 D6 _注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
3 R5 L' J5 w) m' w4 j/ B% w' H& z- h5 T3 ]1 E9 i  k1 D& {

6 ?6 i- G5 q4 u. l3 q2 k: P( v
                            题目, _2 g4 G' w) ~; _1 g% y
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。& C* H& I7 J/ k, ~6 h: A" t5 b% b
第一种方法:利用循环链表
$ W& Z$ V- L, ~9 y2 a3 l! v7 }#include<stdio.h>
4 {; P4 ?+ u4 V+ E+ Z& ~7 c#include<malloc.h>
# @+ D+ Y$ h6 l" m; |: J#define M 8            //共有8只猴子
; h/ f- c# K; D' B3 s#define N 3            //数到3只时退出第三只
) q2 z; ~1 i/ f1 H3 Rtypedef struct monkey; W( j0 J2 p  X# M4 j
{int number;7 m3 ~6 X, [2 c3 z. C; E5 F
int flag;  V1 U) I3 Q* Z; ^2 a
struct monkey* next;
, d( v) z- u( W2 e' |1 M}MONKEY;
( s+ w' q* L' d2 t8 T  R8 Dmain()
/ q# q& Q0 s; T. d{ MONKEY *head=NULL,*p,*s;
- {+ B$ I( _5 K& H: g  int i,sum=0,count=0;
4 U$ I" O6 _  Q) ]8 z  clrscr();              //清屏0 f3 }9 c8 V4 `) F( y, Q$ i* S
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
( v- A3 O' M3 u' s1 X, h  p->number=1;p->flag=1;/ z, E- r2 f+ i) m# C) Z- \: i
  p->next=head;
6 L1 |! P6 ~$ r3 A! s* R7 F  head=p;! K: m9 E" j7 D: s: f, A
  for(i=2;i<=M;i++)! l6 J: j$ v8 g
    { s=(MONKEY *)malloc(sizeof(MONKEY));- w$ r5 J5 |% }
     s->number=i;s->flag=1;
$ _* A, v* `4 V1 v* S) A5 C; L     s->next=head;7 V6 M* ^- A5 c) ^+ q! c* Y  U% d/ z2 I
     p->next=s;p=p->next;+ P3 r$ s0 i4 F3 h& ]
    }
. n3 \" g# ^4 r7 E" V    p=head;2 ]! k2 O( m$ B( Z% ?, |0 M
   for(;;). C5 W8 w" b+ H  J1 i
    {if(p->flag==1)+ J" y. k! f! M/ O2 |1 f# \
       count++;
, q" S+ K7 ?9 x     if(count==N)
8 M& y8 ^, n# i  `: M1 a1 ?        {p->flag=0;! K- C+ x1 h! K1 R
         count=0;
  R0 L1 x9 k' J; H, a8 e         sum++;}+ x, O9 p, U* f  N( A
     if(sum==M-1)
3 G6 z- J6 N# v        break;
) K& N3 Y# U9 ~' E, j     p=p->next;& A% j4 A, L5 q4 j2 x- I% m! C
    }- Q, ^, V% M/ w1 e
    p=
" ?0 t# I7 k  X0 ?# l! d    head;& M/ x! i  {- e$ i$ z
    for(i=1;i<=M;i++)1 T) w8 u! A$ j; E2 w, U/ Z
    { if(p->flag==1)1 Q3 U! Q+ V  K1 S; j7 M
        printf("\t%d",p->number);
8 p! \( d2 x" ?5 @; _4 w      p=p->next;
5 q, K  K# t& J0 k' [+ S1 m- Z    }7 {! X) _/ Z2 [' [- T
* k8 R* k$ O5 N% ^: O
! h$ E3 q( `( W$ s& R

; Z+ W+ d$ y7 N0 w  \; x; P}
1 ^5 `  z- g2 j3 p* S3 w* E
第二种方法:数组
6 e9 h3 |; x. @) d#include<stdio.h>
' \( O" y, F2 w! `0 u#define M 8+ p# M2 [+ }: [/ B
struct monkey
7 M5 z- q% ], A; u% ?{int number;* `8 g2 e) O/ r! D! t
int nextp;; l: t9 {2 D; |/ G3 P3 E( f; \
}link[M+1];
) Z* d4 Z/ o  ~  p4 A/ D, N7 w4 S
void main()$ A9 f+ l0 |( u% v# U% J
{int i,count,h;
2 s" D4 ~% j' Y* e% |for(i=1;i<=M;i++)+ P5 ~- C: v2 h. u5 @. l' n
{  if(i==M)8 e  }( B0 W+ M6 y! q" C! V
   link[i].nextp=1;
; V$ z' t7 J' p0 e/ l   else
6 u8 V4 s; S! U- G& u5 a7 T   link[i].nextp=i+1;3 L) s! i1 C( U/ g; r" U2 h) o7 f
  link[i].number=i;
, y1 Y7 F5 Y. W* Z# i" y! w# [, o. n}
" T# B) C" z4 wprintf("\n");# L2 [& S0 }0 Q% ~
count=0;5 S9 p  ]- {) U. n8 V
h=M;) s5 [) e) b) G- E0 D) {
printf("依次退出的猴子: \n");
/ _" G+ |& z! L: Mwhile(count<M-1)/ A8 b: Z9 S* @( ~
{i=0;5 f4 t; L2 w) o8 p6 u, Y
while(i!=3). A& ^0 l0 n  P( ^% N3 u$ R% M
{ h=link[h].nextp;7 \) b- Z+ L$ g% r+ q$ L
   if(link[h].number)
+ B0 r7 H+ {4 ~; c0 ~0 Z+ j: u# o     i++;}- n. Z- U+ d' {6 W0 A3 e: V
$ E5 J9 ?, I" x; ^7 K2 U
printf("%4d",link[h].number);
/ m1 T+ s- K  \3 d! D9 R* H8 u" wlink[h].number=0;
6 l8 E% a$ A% A2 [/ X) \, tcount++;' X7 r, A5 E. y2 e/ K- b+ N2 M
}
! E( f, j6 X9 e; r3 [
& U+ J; z/ r2 h; p, ^printf("\n大王是:");) @, m2 @8 W1 X3 L) a* b9 B5 W
  for(i=1;i<=M;i++)
( b" q; W& W9 s5 ?$ `  if(link[i].number)
8 `* ~$ k4 D$ o  a7 R+ U7 z    printf("%3d\n",link[i].number);- b1 Q7 ?- e2 \) B: Y- ~& B- T
" x, O; D& z5 v9 C. y2 v
/ h8 Q, e# a/ ?2 k
}
/ A# F. {& q4 t% V1 g
第三种是普通方法for循环
- o% }; F; a% X- J) f) @  c9 z4 b- a
#include<stdio.h>/ x7 W' N3 `" D0 O3 B" |( |5 Y9 d
void main()# }1 Q% z# Z6 T( ~$ B
{ int i,k,m,n,num[50],q,*p;+ a  b& r4 n. N& J2 d. B& \
    clrscr();
$ z# g" p0 ?0 P   printf("input number of person: n=");
4 t& E" k+ n; z5 U    scanf("%d",&n);
. p8 U) w3 S1 O7 ?printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
. v) j4 @9 C& Q! D# I  |9 d+ A    scanf("%d",&q);. t( T/ Q! y% A5 x3 I
   p=num;
! z" i4 e1 \5 K3 p  r  for(i=0;i<n;i++)0 w* d" L! A- s4 h) r0 H
    *(p+i)=i+1;
. I4 {2 V2 O) {/ @$ T/ c' c   i=0;" j; q# J& \# U' j& z
   k=0;5 e' H, k( r/ J$ z# H: m  Z. W& v
   m=0;% ?$ S& f' K/ t" L, x' Z
  while(m<n-1)
6 ~2 X4 i2 q) R. |   {if(*(p+i)!=0) k++;
1 }9 r9 M" v& c8 u! w: G     if(k==q)
; R* E8 N) j3 U5 i' R      { *(p+i)=0;  k9 x9 L( F7 l$ C* Q
        k=0;" E6 E% p# f1 P; |# R5 U
        m++;/ ]+ ?$ g' P5 h( G( c# W8 t
      }
( d6 ^& G9 a+ `    i++;/ p" W% ~7 A( R3 }* J+ L2 \# P
    if(i==n)i=0;& u; V% z1 B( ~# q$ r' ]" b( I; |
   }
: N! z& H: d- P; m5 w8 z  while(*p==0)p++;
. P/ \: h( ]: A9 s3 Q. K: Y  k    printf("The last one is NO:%d\n",*p);
% V4 `5 c6 l: u6 D     getch();2 \- q7 H  Z+ z

4 n% ?+ f# I0 F  P1 f}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
: h7 J  N9 G9 K+ y5 `2 h, f+ Hnamespace 又费马达又费电+ }5 R6 w+ A4 p* o$ |9 ~% \
{; S% z9 i+ K( J0 Z' H# S
    class Program
/ r& l' C$ W, ]* T- I9 N    {
- J, u9 x: g* ~0 E        static void Main(string[] args)6 G% d. M2 p! _* H5 I  ^
        {) t( L6 ^! P( O' L, ?
            int m, n;2 x1 c1 _1 t& a8 W  B: X
            Console.WriteLine("请输入数组长度");; I3 @/ X1 j0 `+ ?  [  B" X
            m = int.Parse(Console.ReadLine());//m为数组的大小4 `, Q& E$ u) y# M: {
            Console.WriteLine("请输入要截取数字的大小");1 F: q" c8 x9 ~
            n = int.Parse(Console.ReadLine());' Z- z4 e' f& x) z% {$ I- d; m9 U
            int [] numw=new int
# _4 K( Q. H( A% U( `5 f
7 U6 y# W7 \1 S+ w1 c&shy;&shy;&shy;;& b; j) X# L- O; v$ V! g
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
6 V! Y2 I- |- F4 _            {
( \# E7 M" C0 x) L: B" K# t                numw[j - 1] = j;" ]8 @7 N' M+ U. h+ U0 p
            }# L! W( K& k: X: `" G) g: b
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!- w8 i! h* C- v; @  z8 s6 ?& i% X
            while (d != m - 1)
+ j, _$ k$ g4 B" o1 O            {) w! \( b9 t4 n0 g, f
                if (i == m && d != m - 1)& f. o" d( ~3 D3 `" S; X& u
                {
4 e8 P  j; b, F9 o0 N4 x+ n  }                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!" i; A6 e* [; h  X6 p  I& @
                    continue;3 s. ]' f' T( t% I
                }* g' J5 b; n( Q" p* a
                else
1 P5 O$ z( {" U1 h7 R                {% |1 ?9 o& o% y: z7 }
                    if (numw[i] != 0)
9 {1 H( o. r. T) K+ }6 q3 O                    {  i# \' u* c* f7 G. I" ], a% `" m
                        i++;
) |5 X9 I/ R# Y. M! q; N# N; X                        k++;
  ^; |. P' m, I/ M/ `                        if (k == n)
6 Q" [8 Z# l! Z# `! X                        {
# J5 u9 i6 R" P. d) Z6 F2 N                            numw[i - 1] = 0;//把在n位置数组元素的值改变了8 r% \1 z3 ~; \7 g8 ]+ e9 ^* n: w' q
                            k = 0;3 w& Y! N$ O$ T
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1& q& V( t' j( \+ m% z# T2 N
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);! u9 A+ u0 j8 r) x- W$ K6 U2 I
                        }
& q+ L+ d- X/ @: G6 r1 ?                        else//输出暂时还没有改变数组元素的值' f7 [; @: j+ @% M; ^
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) n: A# l, i$ x0 ]                    }( G) Y' _+ f" [
                    else  n5 ]; M1 G4 Y/ L+ e, r  R
                        i++;//数组元素为0,直接跳过,不计数。。。3 o2 d4 o" u! x/ L1 Z# Q
                }
: [& }6 x( j0 F9 @
0 e8 r. w' T9 x8 m" V! W' _+ B& X3 I
            }//结束while循环3 v. n( [& H; L9 o/ q/ K0 y0 ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦% d0 n" K% G& ]; G
           
% _/ {1 |. ?2 F$ N+ l1 `                if (numw[i] != 0)& s$ U% {% ~& k1 |( N
                    Console.WriteLine(numw[i]);
4 {3 e  G: A/ S4 J           ; `+ H$ r2 N: `9 W" l" m; b
            Console.ReadLine();
, o, o  _5 n- N! F        }4 O9 q" }" m1 |- S3 n. c3 R
    }
) g; y: W! i6 Y; b0 f  e1 S. d}* d; Y0 i( [, E' C7 O1 ~
小甲鱼最新课程 -> 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-24 08:03

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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