鱼C论坛

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

猴子问题

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

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

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

x
大家好!/ n7 ~6 {" _% d, h. H
这几天我在忙着编一个问题,我用了一种方法编出来!) l6 K3 {/ R3 R- `( H5 @
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!6 @: P  _) v, a" t- L: c+ S3 f' \
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 & s7 v- v7 S( l/ C5 z2 Y

8 F' u8 I/ Z9 e4 t, c) T. c
$ O1 R/ ^& d0 s6 x0 ~4 t
                            题目
. Y, U( d- f! C山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
+ y: l4 Y1 [% f- q第一种方法:利用循环链表
7 g0 W1 `$ Y; E  B* [#include<stdio.h>
  ~, P# l/ n9 B& a0 @: K#include<malloc.h>! G! {0 z! ^2 M+ c# ]1 w2 a
#define M 8            //共有8只猴子; n$ I; J' o; x+ i& L
#define N 3            //数到3只时退出第三只
4 [# O  a) W1 I2 [' K+ y% Jtypedef struct monkey
/ E7 A6 g- ?8 ]{int number;# _1 W5 K4 V+ r8 H
int flag;
8 w6 K5 t7 J/ d1 hstruct monkey* next;
, {1 C1 O3 ^  _2 G: b; J}MONKEY;& [" c; ^! L$ X3 M9 P
main()
! E' b: z3 n1 M6 [  A: _{ MONKEY *head=NULL,*p,*s;
5 L' i. Z7 k+ w1 U  int i,sum=0,count=0;
6 q" P# e# R+ c) f. R( T& m! A' f  clrscr();              //清屏! I2 O' g$ F" _* P; I1 C# f
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存. E- I$ @7 R; |% N% [; _  t
  p->number=1;p->flag=1;
3 x, b  [  y. K+ h8 n0 S  p->next=head;* w6 _: A4 H& ^; ?! \
  head=p;
  P' L) B3 h! `  for(i=2;i<=M;i++)* m) }% i, o3 m& ^
    { s=(MONKEY *)malloc(sizeof(MONKEY));
2 t& B4 V- n' E8 Q) D7 B     s->number=i;s->flag=1;/ ~1 o# O) f; O
     s->next=head;
; d6 `: N4 E( ~7 ^     p->next=s;p=p->next;
" x# X$ ]7 m* q, k, n* V    }
# ]2 j) p* s3 p  ]9 T1 j  x+ U    p=head;* C6 b5 T" B6 q2 L
   for(;;)
& ^9 N/ C. U" P    {if(p->flag==1)
) v3 h6 S# u+ p# z  e       count++;
$ |1 Y6 l# h# D) S, b     if(count==N)
4 Y* o+ M0 i* J        {p->flag=0;
1 G$ y. N# ^0 t( E7 n. l% U, K  Z         count=0;
; }: V# U* @4 c2 _         sum++;}: M9 {& l4 Z. l
     if(sum==M-1): C: S: G( P  L& T% h) E
        break;/ b2 f- C3 x' v' g  L8 M
     p=p->next;
0 H: \# H; C+ e8 X; ], F/ Z& K+ }5 _    }: t* C# h0 y- M$ N6 G/ ]# F  S- |
    p=
( [$ p/ R! K. \6 T, m    head;( l$ W( q. V' `9 T' z* u
    for(i=1;i<=M;i++)+ A4 S, z2 H# }
    { if(p->flag==1)4 j* M3 [$ X+ w; s# B4 u
        printf("\t%d",p->number);4 y( F3 I6 O" x# A: i
      p=p->next;1 {( y$ e1 U* l- x
    }
( s0 u' W" l& i" j: I9 z
3 @7 I& y) e+ u. I5 i4 y
# o5 f3 b5 o# Y2 k, J. }( o/ C  B; i/ d/ `& x! A  D% `6 Z2 h
}
) X, O& V' O" G8 B% b7 ]
第二种方法:数组
* g4 [1 t# A1 ^& g#include<stdio.h>+ v; f9 C) \# z* {/ W
#define M 8
6 h* ?1 }% d$ b2 Istruct monkey
. a) X' h0 A% I2 y# R/ E{int number;
' p% F. E/ ]5 w2 x, D. Zint nextp;3 L. {; ?+ W* H  ]" {
}link[M+1];0 X# U2 J" p) f0 a* z6 A, m5 b
* w% J+ X  _& @
void main()
0 b" b# s" W  Y, Q{int i,count,h;
2 L; e2 F& |: ufor(i=1;i<=M;i++)
& ^# S! j: o, z7 _, y! G% C{  if(i==M)& s/ X- G' G% |0 p3 p
   link[i].nextp=1;* ~' s" I  W' U8 g0 |5 p
   else
0 H+ P' r+ a8 `8 E2 Q2 C   link[i].nextp=i+1;
, W7 ^0 W& s! f  link[i].number=i;+ @* h6 P% Y+ D8 P5 K  i5 d5 }$ \+ H
}6 \$ o1 {: _/ A* C6 R% o
printf("\n");* f* D) v% x; g: p; r; ]- Y
count=0;
: I4 r6 J4 S3 Qh=M;) \$ t. N& K1 l  z$ H8 H' L$ R
printf("依次退出的猴子: \n");7 X5 Z8 ^- ^% |' k$ H  K
while(count<M-1)
  j. O& N$ _3 \4 X{i=0;- x: @9 S+ Y1 g6 S# [) ?
while(i!=3)& ~9 i+ c- O/ D, W- v* d+ S8 y  M
{ h=link[h].nextp;
4 n* S$ @- q/ t, k( k6 ]: K   if(link[h].number)
; W& l" O: C; J2 m: |+ V% X     i++;}9 j2 Y& q" L" q& X7 M$ m7 T

6 h( ^4 J- Q& h$ l7 r; tprintf("%4d",link[h].number);
9 p: b) m/ E) U; k; \$ z- ?link[h].number=0;9 W: z9 x; i0 U
count++;, R1 B4 n" m6 Y3 o! m- ~+ w
}1 M& c9 e; {8 z2 r  Q& a: G4 m" x8 S
$ Q, S, g) N/ B5 a# Q
printf("\n大王是:");% C* A: i, p8 e% z0 @$ u5 N
  for(i=1;i<=M;i++)
1 u9 b2 P; b0 V7 t  if(link[i].number)# k4 o0 ^$ ?# ~
    printf("%3d\n",link[i].number);
$ F* L: `! a- H
1 Q5 K$ U' y, d' I2 @9 \. z: d4 T& y) ]$ M: V( T
}
$ S' w! Z( ]& x" B* M: k
第三种是普通方法for循环
# q% O  o& }( j4 t4 i) U
#include<stdio.h>
- l% q$ v. @3 f% P* x2 _void main()
4 ?6 ], P+ ?2 ^4 r{ int i,k,m,n,num[50],q,*p;5 x+ K+ i/ }  o. x% {6 c
    clrscr();
3 _# c1 p$ e, i& C   printf("input number of person: n=");( N- H7 M$ Q4 Z, T( q
    scanf("%d",&n);( k3 E6 i) t8 t6 R4 o
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: u4 M4 V5 N2 E* z4 K    scanf("%d",&q);
0 j$ o; R& ?; Q8 l& G   p=num;
% M: K2 {& g  H; r/ @  for(i=0;i<n;i++)- f( S3 I! f/ c1 f/ `% k4 x3 h
    *(p+i)=i+1;# Y) w4 E: B" A$ l7 B  h$ d
   i=0;0 @. t2 z2 u6 r+ U, P
   k=0;
5 b( S% |; R  @4 c/ F   m=0;
6 l% Q- N! B& o- M3 I  D  while(m<n-1)- p/ f3 N; z: i4 B
   {if(*(p+i)!=0) k++;; D/ t: a9 e% N! u
     if(k==q)
& B* @( ^: T; v& d# i9 @      { *(p+i)=0;% D* {/ a! g4 A: ?, F& m& {
        k=0;
( U* ]7 G. @5 q# x: E  @        m++;
. i, t7 q+ G7 q2 S- ]      }- c1 F. c. h4 T( R3 z- u
    i++;
/ \5 u; Y1 b: Y9 o    if(i==n)i=0;
$ ~4 N/ b" [6 g  W' a9 q; v8 W   }% `3 A( N( A8 I* U: q; d9 t7 A
  while(*p==0)p++;
  z0 j" [* z( A: h/ }, r% L    printf("The last one is NO:%d\n",*p);
* t( O: h5 K; E6 O  _% g9 P2 }# z     getch();
. L2 X5 R, k8 Z  x) V! A/ m' h
9 i) F' U7 B  X4 O  Y. y$ ]}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 s5 d) w( W( jnamespace 又费马达又费电) U9 L, O+ F' m+ |
{  \5 J, }$ i, c2 k5 @
    class Program
4 t, D, I  X  f6 Z2 N6 f    {
: Z5 e; h( M! y0 I& u        static void Main(string[] args)# X/ ~2 H7 _  i; h+ X9 i4 i& N
        {: `; F8 i, ~. x2 l; X' k# u
            int m, n;) u9 ^: V$ o) b, Z3 @
            Console.WriteLine("请输入数组长度");4 W% c; @% @) U
            m = int.Parse(Console.ReadLine());//m为数组的大小
5 T' _, B) H/ i9 h            Console.WriteLine("请输入要截取数字的大小");8 @. [& W! E( h1 G
            n = int.Parse(Console.ReadLine());
5 G, k% Q' Z" w$ I3 N' R            int [] numw=new int
$ T1 Y. n4 E2 u# J4 _. y* g8 I
$ X/ t4 [  b- E" _- h&shy;&shy;&shy;;
/ f. i: K" c' i            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数% l8 V1 e8 d! e5 q* E7 B
            {
1 }8 I! w" a+ G. O                numw[j - 1] = j;' P' j: m# G+ L2 m- P
            }
2 Y* b/ u/ M" Q            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
- A' D* U* L" \8 Y, L            while (d != m - 1)
: @. C5 u& a, @            {; C( p% N" s8 y" a
                if (i == m && d != m - 1)" M' d# K; @) R0 y
                {8 i5 `0 ^7 }! Q% z" d* }. [0 M
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!) @: T1 l4 _5 e+ H
                    continue;  M- C" ]- V1 [! q" ?# @
                }3 t3 ]6 T# b1 z* B7 W6 r0 p( s
                else
( B9 j4 S, L) q( a7 ?! N# U. J) S                {
# _2 I/ Z8 \  l7 c0 f* A( V                    if (numw[i] != 0)
7 a0 ?6 e& _! Y2 K1 a                    {7 a! V* o$ c- L2 U0 R" d: F2 W
                        i++;
8 y8 F6 K, A5 I: B) L! \% x3 |. C                        k++;6 q9 h; F& M3 L( t4 F/ M8 \
                        if (k == n)
0 I* U. S2 ?/ R- S4 D8 z6 d; p                        {
( u8 d* X' f' k4 d' M4 T9 f                            numw[i - 1] = 0;//把在n位置数组元素的值改变了+ E% ~4 J5 W6 j$ y+ z2 k, M
                            k = 0;1 z/ S5 l0 H+ T: L/ D% l% J# L" m
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1. g& J  |1 q" O/ R2 {
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);# o& m% \) c+ x" t: V0 D7 q* R
                        }
/ ?6 {! L7 T% n                        else//输出暂时还没有改变数组元素的值) X( M5 x/ ]. t9 f7 Z  ^4 b1 r
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 O+ ]- }3 Z  s$ {2 d
                    }7 s' g( H6 T; Y! K! V, v
                    else" C/ X7 k3 ?2 w7 c  L
                        i++;//数组元素为0,直接跳过,不计数。。。
- _8 S; T+ B( o3 ~                }$ t8 d5 m$ [& _7 n) s* W' v

! g* |" z, H3 I$ D: i2 S- `2 n) t, ~3 O, \+ s. L  v/ m
            }//结束while循环9 V) X5 ^% D% h. h0 V: |0 A
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦) O- ~6 k6 h. |
           
/ q+ {, \) c/ r" J+ w                if (numw[i] != 0)
0 l& [: M1 K- ^+ C# M                    Console.WriteLine(numw[i]);3 a2 M# `* l% g, ?
           # j; g. Y: w# Z2 P; E& k1 c% b
            Console.ReadLine();
0 n! K* O, h+ S. P        }
6 |, K9 f  b+ F% E* x2 C# h/ w7 j    }
% s! h3 w5 g6 h# H  @% T. x}8 F+ ~- C/ k$ \7 k% 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, 2025-10-16 23:27

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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