鱼C论坛

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

猴子问题

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

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

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

x
大家好!# ?$ D3 c  d; @/ l7 Q9 i
这几天我在忙着编一个问题,我用了一种方法编出来!
4 `  B% b- c6 ~4 R7 g但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
* c3 P2 O4 ^& B! ?$ R% E3 f% ~注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 4 k1 q- G. |* Y( b) z( Y

& S1 ?- m2 ^1 Z/ [$ R$ x" f+ W5 r+ `0 S/ u9 y! k. X4 q$ p3 X7 G
                            题目
- y+ O% S3 Z+ Z) x山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。& m: W+ N! h+ d: V1 S2 a2 k
第一种方法:利用循环链表: t! \" m" F  B3 ~
#include<stdio.h>
( Q& q9 M- r+ q% O& t6 x! H' V#include<malloc.h>
# s& S. Y8 p/ v#define M 8            //共有8只猴子7 v' `2 ]# V+ t3 X$ N
#define N 3            //数到3只时退出第三只* U( C$ ~" X' c
typedef struct monkey
0 m2 I+ W; n7 J$ s+ i+ k2 v6 V{int number;
. Z/ E" }8 F" {* ?& Q9 nint flag;
) y0 h9 S- I9 T+ D) Vstruct monkey* next;
. ]8 R" W/ W* J- h* Z5 o}MONKEY;; a0 g; ]* ?* [
main()/ Z2 t- f. f8 A# w* ]7 X, f
{ MONKEY *head=NULL,*p,*s;2 k( x8 I& V, F
  int i,sum=0,count=0;
( c! b! O0 s  B. t5 T  clrscr();              //清屏# R' N; P9 U4 j6 N- K
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存+ k5 l$ o% X) c6 L( n
  p->number=1;p->flag=1;
% t/ [) @$ Y/ [' b; `  p->next=head;
8 W! ^1 o2 x* \8 C6 i( W1 O, G3 e/ `  head=p;$ Z) _  \: M9 _8 J
  for(i=2;i<=M;i++)
0 i* X, L8 ]' F1 h    { s=(MONKEY *)malloc(sizeof(MONKEY));
) R4 d7 j% M7 H& ?- _) ^6 A     s->number=i;s->flag=1;+ {0 I7 @$ a% a# V7 d8 f$ R
     s->next=head;, y+ ~1 c! u9 H! X, z7 }- S
     p->next=s;p=p->next;
  t8 ^- w5 |8 W: x8 \+ t    }
6 [4 h  P2 P0 h    p=head;
! j" e1 ]' r9 k, ^$ j   for(;;)* ^; p9 X5 y" j- q. Q- Y/ _: t5 D5 m
    {if(p->flag==1)
5 z: U0 D$ a6 ?2 q# Y( z* P3 v1 p0 a       count++;$ R- G3 T. e, n9 Z" M; ^3 p, A
     if(count==N)% c8 {3 q1 i& D
        {p->flag=0;
) E( T% G& H+ Q0 K1 w         count=0;  l# G) ~; h( j% E
         sum++;}
' ]& n* U6 _( O2 L% v( {5 ]& {     if(sum==M-1)
& S8 Y3 ?+ b! e        break;
7 M  u7 S$ p2 n. R: s     p=p->next;
/ K( p( }7 {' L; n8 N    }
. M4 w. ], p5 I5 {& [; b    p=
' @' i$ w. T+ N4 l9 h; s# G3 V$ `    head;
; Z; |+ p! l2 e% n! b0 j) {    for(i=1;i<=M;i++)( x; G: x. T) X0 T% N
    { if(p->flag==1)0 \1 ^$ q. ~& s
        printf("\t%d",p->number);( p6 h# t% g3 _- ^& c5 S6 u5 _
      p=p->next;; [- T. K3 h0 j5 {  C' @: ?
    }9 D0 r# `9 y+ `
0 [& ]- {8 j  b! b* B

- }9 k9 h* b/ }( Q  m( ]/ G9 n& v# T1 O+ M! a3 |* E
}
  Z' d; y& D  J+ x6 u+ U; _  j
第二种方法:数组
/ w% m3 [8 R2 q4 c$ k#include<stdio.h>
2 P: u- H' @( u2 v( |4 t#define M 85 L8 R$ F; l  ~5 u& v
struct monkey
) B% F2 f- c* J# N3 ]{int number;
% o9 {& ]. x+ M! I* Uint nextp;7 @8 A9 U; [; b8 e
}link[M+1];
! {1 T1 T2 O9 `7 z2 ]6 ?- d) \' Y* |* ?; r( A' V5 E  I4 g
void main()2 U$ r: e! X+ i; c0 \
{int i,count,h;
7 w0 q7 V/ L; r3 ffor(i=1;i<=M;i++)
& y7 u5 r9 t- ]{  if(i==M)
* l/ P! @1 O3 D+ z   link[i].nextp=1;; O( s- X3 M  S* ~! p, G5 p8 P
   else* A8 u: q" L9 O
   link[i].nextp=i+1;& ~  E& S/ L$ ^! H$ k: Q) ^
  link[i].number=i;! o3 R; U# f2 `# b5 L: |
}
7 F: v' k$ z6 d) S* vprintf("\n");
+ x, v' Z# B5 ycount=0;0 v! `! R! V+ W) m: A3 D& l0 D& H( o
h=M;
1 O# }/ P$ ]1 C0 mprintf("依次退出的猴子: \n");# r0 u' S9 b+ x
while(count<M-1)
! x# C# p1 L# B% o8 w{i=0;% m1 O( w9 N1 B: ^2 o
while(i!=3)
& D  U' D' ?, P& w. q+ c7 I' E{ h=link[h].nextp;
6 h0 a' f  X7 b* e( I   if(link[h].number)/ m. Y( `+ i; E6 i% E
     i++;}
/ C& S$ p+ t: s0 [* t3 y
0 s, |, c) D+ ~7 @. F7 L& w# `( |printf("%4d",link[h].number);
, t8 v4 x; ]1 X/ nlink[h].number=0;
9 Z4 v, V" \& v8 ]' V# N) hcount++;
3 n2 c- z4 |7 }0 L6 S& }}
0 u& t" S. q  ?5 E. g# J& ^2 @3 c8 D3 W9 C- T* `
printf("\n大王是:");
1 W  P/ T' y6 r8 I8 f  for(i=1;i<=M;i++), {$ x  E/ ]& g$ Y
  if(link[i].number)
! K- X$ o% n& v! A) a5 ~! U: @    printf("%3d\n",link[i].number);
0 K2 A! y- [9 Y) b. v
2 y+ N9 k8 z( W" \- a1 g, N) ~0 |& _& r4 o8 j* s. l
}
& m4 S+ j9 a/ ]
第三种是普通方法for循环
/ z6 K" E& O& W- r* S* w  \
#include<stdio.h>% s  i0 k% U5 D
void main()* V& k: [/ d* \6 v
{ int i,k,m,n,num[50],q,*p;
5 h/ J, ^1 I  \! {  w( L" m    clrscr();
. g  w$ v, G1 b* @9 O* ~   printf("input number of person: n=");8 a5 @3 \# v" I3 H: }
    scanf("%d",&n);" [' W, T4 c& x6 s7 ~
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
: I0 V: G% q% v" @7 K    scanf("%d",&q);2 A! w6 S& e& H
   p=num;- X  B9 M" q/ G/ g  i- g8 f
  for(i=0;i<n;i++)/ }) U5 U7 A4 s  V3 q+ r
    *(p+i)=i+1;
1 B) j2 k( ], H3 P2 Q4 [   i=0;& R+ r+ O9 P" q$ _. F8 U
   k=0;9 y+ Y  a, H8 S$ C
   m=0;) |4 l& H. L/ M3 D! ~/ f  j. |4 ~; Z9 f) K
  while(m<n-1)
. }% V' g+ g) b1 ]) `! f   {if(*(p+i)!=0) k++;2 S: V9 u: C4 f
     if(k==q)4 i8 d9 ?0 r# n2 e) y7 T
      { *(p+i)=0;8 s3 L. {2 y* P
        k=0;
( O( r  l/ Y- `5 _        m++;
+ z; f5 ^7 B9 N+ z7 T; P- W( ^      }  `/ s5 c8 B( C* E# a! t
    i++;
) A& _: p$ P; e, `! y0 f. r    if(i==n)i=0;
% p+ P0 i+ c: |+ a  I" x   }
) R- {! N# ]: Q6 x" Z  while(*p==0)p++;. u7 Q" R) d2 }1 {+ x' S  q
    printf("The last one is NO:%d\n",*p);; i* u  f! G0 C/ }2 @6 ^
     getch();$ Q: k  n9 h- \- h! d5 S
6 I: _8 v* O6 ?
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;! ~. z! \( a* k  @4 j/ P
namespace 又费马达又费电% ~) C" A6 s; _6 J9 W
{
% B; O: r! f' E, l# A6 v) [! s    class Program
( H0 x1 j) s, D- |$ h    {: K9 s5 Z' _7 m/ Q2 r9 h
        static void Main(string[] args)3 W6 ?$ m5 z* g2 I& A
        {! j4 V3 q3 j7 Q# Y
            int m, n;
# a7 g' O+ u# z' W: j; l/ Y, L            Console.WriteLine("请输入数组长度");4 Z  e/ |$ X1 g; U6 `) E3 ]
            m = int.Parse(Console.ReadLine());//m为数组的大小
/ i! Z4 w3 E" f2 `2 x9 V3 b            Console.WriteLine("请输入要截取数字的大小");
5 N2 r4 u0 J' H4 W" n' j            n = int.Parse(Console.ReadLine());* c/ B/ I  x$ {% I* r
            int [] numw=new int. k# Y  j/ Z( z9 \! ]

1 w, j: g* \8 N+ W5 r&shy;&shy;&shy;;
$ D5 {1 y3 z/ `$ ^+ U2 O' s) p8 m            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
+ C- O  o, Y( A+ O1 k3 q            {
3 v  H& q% K0 y3 q                numw[j - 1] = j;
3 f0 |  C* ^- z7 ?* x$ W5 e* a            }& Y. Y1 B$ [  t  c) _0 B8 `! q5 i1 \& c
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
" }& ~; Q/ ~" }            while (d != m - 1)
% k2 `. M' a- t8 p5 L( f! y% `  Z            {
; ]7 t5 M# G, z% {, @* ~) c                if (i == m && d != m - 1)
; q" p# V3 Z4 W& F                {: C  [- Z& A8 D0 I7 W7 _
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
  U- `, Y6 V. f) M                    continue;
6 D0 @% R; C3 ]" L9 l+ {                }
0 M4 q( j1 D; H- [( ]: P- [                else' [# o& t7 i. H1 t
                {
. V" z, g( _  k" p( z4 F% v                    if (numw[i] != 0)2 Z% w3 A5 e  @, r* x
                    {
# `$ T% w* t$ r4 ]8 @                        i++;8 ^* B% o: a" N5 K
                        k++;
4 r* U0 M5 Y  j! v9 c" ^9 ?                        if (k == n)+ C9 D( \( X* B" S5 R
                        {
/ p  G8 I. T8 Z- v0 u                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
6 B: \* {8 U* h8 e; f8 I! U. f                            k = 0;( t0 [0 V" W6 k; E
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
, W1 q% k4 a. `3 u1 o! `                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);, K; v6 N+ a( U8 ^- r
                        }
% V7 c* m6 K' `% D3 I  d$ W$ `( g8 k                        else//输出暂时还没有改变数组元素的值3 e& `7 |5 c& `$ `* i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
6 L5 J  _. f' p, [8 r" |8 C                    }$ ]9 A# t: S6 i; ?
                    else" l' B0 R. P5 R
                        i++;//数组元素为0,直接跳过,不计数。。。
8 c' C' K& [" \. T                }
' S' K8 i' W& J% P1 W9 ~
2 k4 E  d* Y6 z$ G+ l* H, R. `2 X, N7 K4 C2 P/ J
            }//结束while循环
  Q2 v7 ~, C( r& P: E. B            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
; u. s+ J. f* q           
" \: F: t' ]0 ~, Q                if (numw[i] != 0)
4 Q/ Z  G) p( e# s- a' J: ^                    Console.WriteLine(numw[i]);
, f* `" `7 u) A- D. g, e% f- {           
/ E" r; D/ W) T: U            Console.ReadLine();
& ~5 B$ s0 V5 U: ]. a        }
! i$ Z' q2 k. I  l    }
; n3 E- P' |- [! B. E}
! P9 K" ^8 F9 ~& ^3 p
小甲鱼最新课程 -> 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-7-19 07:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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