鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' |) V' k" f/ g( j$ W* A0 d这几天我在忙着编一个问题,我用了一种方法编出来!/ b! I- w1 ^2 S- S4 S2 _
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!, Q7 F* p! j1 a  \1 F. p
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 % y! G* }$ ]7 l* P; w- ~( U2 j

  I% j. \9 B" J4 C, q6 _/ W" `, O" O: O' |3 ?
                            题目
0 @* |( I& c  R3 m* b+ w/ o山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。* v  n% p- ?; v, X
第一种方法:利用循环链表+ q" s5 Q) [: P8 z1 N, M& n
#include<stdio.h>
/ V7 U( K5 m+ s& Y#include<malloc.h>
" j: V* w% L) Z2 f; ?6 Z9 D#define M 8            //共有8只猴子
6 v% s7 m* [  h5 ~* K#define N 3            //数到3只时退出第三只
4 t  t" l1 M& s  otypedef struct monkey! @/ a- Q2 s7 d) H% r
{int number;
" u0 O5 r  o5 t1 M6 z; hint flag;
; f* A/ K6 q1 j, Xstruct monkey* next;' b/ @  [) h- @; h% k; s
}MONKEY;
  K0 L1 q# ~/ g7 b% |4 pmain(), d: d" v4 L1 T/ [; p6 @
{ MONKEY *head=NULL,*p,*s;
" [' x; I+ O- ~" `  int i,sum=0,count=0;
0 T6 {) R5 m  r3 z  clrscr();              //清屏& ?" x- _* C" A6 F0 r2 Y6 K5 y) C& {1 F! i
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
, b! [2 j! U) y" Q7 Q  p->number=1;p->flag=1;4 M4 {! R! Z+ ~6 j
  p->next=head;
5 E5 a6 a; h3 h% G1 B# |3 L1 E  head=p;% u& I* w* s! {
  for(i=2;i<=M;i++)9 n! k6 Y, V$ r( Y* a
    { s=(MONKEY *)malloc(sizeof(MONKEY));/ E' }6 y! b8 }3 z: l: [* b1 f& n
     s->number=i;s->flag=1;
( C7 K( J- g% H0 Y     s->next=head;
" Z0 x, U4 D% b( k; V4 j& }" z$ K     p->next=s;p=p->next;
- D/ Y% t. f6 [% G6 g( S( Q$ V    }  R$ y" P# f" F3 m0 F
    p=head;
1 O' [& Q. t6 [- V6 n   for(;;)# {1 a5 q0 C" Q: U5 h. v
    {if(p->flag==1)3 A9 T+ \! O! f* E% r. u
       count++;
4 t* i* @, _4 G, |2 O( C7 O4 F) d     if(count==N)
$ }7 V2 C$ K  j        {p->flag=0;
  f$ a5 f) y6 P8 F         count=0;
2 }/ L% ~$ S9 J3 w         sum++;}1 O( ?3 D5 \4 I! K0 y6 ]+ k
     if(sum==M-1)0 T. b& p) _" E* l, \
        break;# Q/ x; D7 _) J
     p=p->next;
) D' q# ]3 D' M$ U! a0 B) B    }
/ h+ Q. X! f, K/ m3 `    p=
5 M5 z, d. b4 ]/ @2 O    head;
6 `, j% W4 d' e- ~    for(i=1;i<=M;i++)- p, t/ e- u/ I+ a  H% k. |
    { if(p->flag==1)
- F- l$ P! E8 K        printf("\t%d",p->number);
" {- j% p! V8 m/ k9 Q      p=p->next;
  `) U- F3 h4 I. w! N    }4 N  q. U+ S2 ^+ o* V
/ I! [& [( U7 f3 E& v

; i" b% l0 P8 l" P* |1 P+ g4 `, m$ p5 u4 P: y3 E
}
8 d+ P9 ]5 ]$ F, L
第二种方法:数组
" ~4 n, E0 B, {( t7 Y#include<stdio.h>
# I* w8 D" h' g  w#define M 8
' u$ C$ L# ?# B) F' ]" zstruct monkey# R$ s! Q, y- H1 a8 U* V9 `" a
{int number;# B7 d6 ]' h+ N6 b2 N* f. M
int nextp;1 Z* I) p, ^* _7 c) I3 d
}link[M+1];
9 P4 ?/ D0 M/ s: D/ G/ j1 O5 D
8 q; ~- X( Y( |& cvoid main()5 @9 f. s" x5 y% z9 \0 S! r
{int i,count,h;) }0 N& [6 Q1 x1 C/ ?
for(i=1;i<=M;i++)* D* B- J# ]0 [8 Z- C) a- E0 u
{  if(i==M)' O/ \6 V* h' z1 X, I+ k; j1 z
   link[i].nextp=1;' O- k) m3 s1 g: [$ h
   else
0 `* K4 ~) `6 v0 j1 h9 f4 G% v   link[i].nextp=i+1;
! [8 ^8 y& ~% l* j; C  link[i].number=i;
& q8 M9 n, L6 B& ?$ X}
# P/ d" i  H& t" fprintf("\n");9 J. s! @1 f6 u5 L8 P: x, u
count=0;* w) {( M' L8 v+ ~' z2 q
h=M;
. s5 G, M: p4 J% Aprintf("依次退出的猴子: \n");8 _- A& z/ g8 d% d9 L5 r
while(count<M-1)2 |- ?9 j/ Z0 C5 l8 G/ A( L
{i=0;
; `  z$ R3 _0 A& Iwhile(i!=3)
, X7 }) m+ R, M2 U{ h=link[h].nextp;: b1 K6 B$ P) |7 M! k! a& {
   if(link[h].number); f# ~. I2 s' s6 S" r
     i++;}7 E; j! V; G0 s4 P! B# B! s& H
  u4 [+ F+ Q  t7 t7 X& e2 P- d! w4 F
printf("%4d",link[h].number);- r5 e" n" G4 d" E
link[h].number=0;7 a  `" e. B6 @# i! e! f
count++;
" C' S* X+ |4 u7 ?7 p' o2 B$ Z7 x}
, n7 y- P/ \/ E' z2 w! I3 ^
3 O$ c5 [: a7 E3 p6 _printf("\n大王是:");
3 R+ Q6 n' L! x" C, j  for(i=1;i<=M;i++)
3 y0 A. b5 @, O  {# `  if(link[i].number)- O5 E& Z' }  P4 ?
    printf("%3d\n",link[i].number);
6 n0 `  V0 J/ S& U: B* B8 H7 U2 A  h. s+ C
8 A" P. s# t5 i+ t- ^
}
6 @( D9 R8 K/ ^' m3 E- A& y
第三种是普通方法for循环

5 K( ^1 K4 T  Z, n9 w0 }+ e6 D8 Y#include<stdio.h>
9 A' [, E  n3 ]) {void main()3 P& J0 O/ r' S* B& T
{ int i,k,m,n,num[50],q,*p;
2 N. y; r' @9 ~1 ?    clrscr();
# I4 \% _4 @; X) }+ X   printf("input number of person: n=");
8 M+ g& A( d3 z( S) G! X+ ?    scanf("%d",&n);
! r7 O7 T1 i1 J; @printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
' @* `8 L5 d! g4 k3 M    scanf("%d",&q);5 h1 I/ t! g+ i
   p=num;
9 n' V# J& K. h" K* s  for(i=0;i<n;i++)
1 g- P& o* `: L- V6 D. x% A* U    *(p+i)=i+1;4 q1 R" H) u* Q& c% q
   i=0;5 q8 c6 a% ]9 P' v6 ]% G
   k=0;& x* d) e; k2 `( I( {
   m=0;
3 I4 j  J' ^3 A+ D1 O. k  while(m<n-1)' w. {. @; k* o! S8 }/ u
   {if(*(p+i)!=0) k++;& F3 b3 r9 E6 l/ x
     if(k==q)
( o0 O9 V: j% l; n) h8 V      { *(p+i)=0;
0 R" g# o+ Y% E2 a        k=0;
5 E( P1 ~/ R/ C# Z* Y        m++;: S" Y8 V: B4 `% x$ B% h9 T  S! D
      }
1 S9 P4 \* B& K- W% o    i++;6 B4 Y" {! ?# d7 ?
    if(i==n)i=0;
3 b0 \& C: o3 H6 d% g   }
$ h; h, b1 U2 j% J3 I, D/ M; Z  while(*p==0)p++;: _5 {2 K+ M! z8 Y0 l
    printf("The last one is NO:%d\n",*p);
+ B" r* L3 ]. E5 l; _     getch();1 j# S  X) s/ e. f8 f) k# d6 ]

" t6 W; H% a2 h% ?' }% [! k/ E}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;# w; W8 i  k; @
namespace 又费马达又费电8 [, Z  g* U/ O3 [8 E  p# o
{
9 e  z# x+ \" s9 T4 }( V* H    class Program
0 H$ g. f, J4 p. `    {
: Z+ ^2 a. I3 K& I5 A) y5 j9 J        static void Main(string[] args)
; F0 Q* F! w4 l/ b1 o: q1 v, D        {  v; Z7 m6 T8 s7 V# @
            int m, n;& e' f+ |3 o- [$ N8 n
            Console.WriteLine("请输入数组长度");
5 D" ~4 A$ E! ~' y- `- b$ ]            m = int.Parse(Console.ReadLine());//m为数组的大小
) U3 r; y0 q7 q- @+ ^# y            Console.WriteLine("请输入要截取数字的大小");  A) s5 y7 e8 {
            n = int.Parse(Console.ReadLine());9 Q, H) f- l! m3 [! d
            int [] numw=new int5 z# m5 |+ a! x6 `- x, }

- {' [( q; u4 W  h4 {* ]% P&shy;&shy;&shy;;
2 i8 c4 H6 |5 ^$ n            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
1 l- f% H9 }' _, w2 w+ g: f  b% [; R- L            {
* n) U5 ?1 A9 w4 ?6 t                numw[j - 1] = j;
, e: x1 G. Q2 A; b            }2 f% B! Q' z4 a! T
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!6 ?% g% T9 O, \* v( b; ?( [: N
            while (d != m - 1)
  d2 C" J5 I+ A0 |4 g            {4 ^4 k  p- l# L3 h* C
                if (i == m && d != m - 1)
' ]9 L* b; I/ z2 [- z8 Q                {
! K# J+ Y7 g& |; r- n' Y4 ]" @                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!. s7 Z' P+ c% ~6 y
                    continue;
; s) ~0 N# _; T/ i/ g                }7 u  Q3 B- X# Q; J/ [% @+ E& o4 a; b
                else/ j: f( q; N' u$ M8 F4 {# B% {
                {
  o. J; D. h$ @/ f5 w                    if (numw[i] != 0)3 @" u1 e% l4 `1 {" V1 g* u7 S
                    {
* s* G! e; \1 a; n                        i++;- G; i: p$ _6 q( C  D; w4 e
                        k++;8 _  f$ {  E4 w/ l
                        if (k == n)7 S1 }# t7 h/ h
                        {. F4 [3 |8 B$ s% W9 ~
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. Q$ P4 `/ D! c2 L- D+ h
                            k = 0;2 s5 O/ L1 N: U! ^" _- w
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
$ s1 t" N* ?- o9 _8 o9 N                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);7 ^& Y- a! [' g4 E
                        }4 \  ]) o5 R# A' k; F0 Z5 z4 A
                        else//输出暂时还没有改变数组元素的值7 o3 E1 k5 J: B7 ?% M; k
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);. X! G: N, Y! i& @; d
                    }
. A/ z- N3 ~5 U- d* x4 @* c7 f                    else8 w0 h# r) ]8 `
                        i++;//数组元素为0,直接跳过,不计数。。。: m* I% X5 _- W9 v1 h
                }
" i" `, N( d- x8 |( P2 Q2 y
: ?# j9 a0 M& m6 S- \; P. X# \9 ]! @$ A0 K
            }//结束while循环! v' a% X/ R* Q$ {8 f; c
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
1 M( `. d  G' m& I. c* x5 Z; t           
1 W/ \: {5 X% b4 w1 b! v                if (numw[i] != 0)+ y9 R$ A0 C$ {$ R8 V
                    Console.WriteLine(numw[i]);+ e: Y/ K9 [2 u: Z8 P7 a- ~
           . {+ g( c# v  y% L8 s2 V( Q
            Console.ReadLine();
/ R. A( S0 g: K7 C8 e+ Y        }1 X: r& d- v* w8 v; Z7 ~; I
    }% |/ z9 Q1 \8 G0 ]* t" V
}
8 `; R1 H" b* U) M5 A$ m$ ~' y( o
小甲鱼最新课程 -> 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-7 00:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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