鱼C论坛

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

猴子问题

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

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

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

x
大家好!
3 y  i2 v; p. }# p% S/ R* @这几天我在忙着编一个问题,我用了一种方法编出来!0 w0 u3 T) `$ Q. `, ^0 w
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
' \' C; i- A3 j5 @# q注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
" |7 ?' f3 r& N- ^  @, {) A& j, T. u/ W7 [

* E( u- B2 A3 d: q4 u; R* H/ n
                            题目
' j6 r2 U4 i0 V" I+ a4 _9 a( {山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
! K2 ~$ X  z8 l% M. N: k. p8 e第一种方法:利用循环链表7 s6 l' |; l0 Q
#include<stdio.h>$ _* |4 |9 O. C8 t" J( n/ Z
#include<malloc.h>: @" A3 ?$ V) Q2 C( I% `
#define M 8            //共有8只猴子
, ^: V' g6 J- G3 \2 R! v' D#define N 3            //数到3只时退出第三只
7 B( B5 R( Z& v/ O* atypedef struct monkey
5 b& I# Q7 G8 _9 Z) N& g- p2 I- o{int number;# J2 D7 u9 u5 e+ w3 l* N
int flag;  y2 ?# T7 i0 T/ B+ r; w
struct monkey* next;
. `5 r+ T$ U3 W. C8 G}MONKEY;
  x4 I  W9 k% S7 `, X5 ^- dmain()5 I0 V# z  m3 e: C
{ MONKEY *head=NULL,*p,*s;
; U* `  ^2 t% N+ \7 @0 _9 k* \) ~5 i  int i,sum=0,count=0;+ m, a3 `! H) r; K% n- _( [
  clrscr();              //清屏6 `4 c7 Y/ e; v! M( q( u
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 }& Z# Q" V- s9 u4 X. r
  p->number=1;p->flag=1;9 a6 U5 Q: v) E7 e6 y1 [
  p->next=head;
1 O8 W0 g2 D9 v8 p# B; b( p. n2 x" I  head=p;
* ~" p2 l4 S. `5 K  for(i=2;i<=M;i++)0 d- T( P0 b: L# k! ~6 g$ k% H
    { s=(MONKEY *)malloc(sizeof(MONKEY));
+ O' j5 @. g9 |     s->number=i;s->flag=1;
" G* }7 j/ B" R) b     s->next=head;
; ~' U8 Q2 H0 T5 R     p->next=s;p=p->next;2 G6 x$ `- g0 R" f" {% Y
    }( ~, v! O2 r& `% b6 A
    p=head;6 X8 ~# F. w  }. K
   for(;;)
* v1 `$ k9 z  u    {if(p->flag==1)
  E$ P* s* c/ y1 V3 \  @       count++;, @% j' R2 C. V0 B
     if(count==N)3 K3 m; Q' l: i7 q
        {p->flag=0;
. }% L4 h1 t9 J0 `# T+ A8 a9 E         count=0;
0 W$ F- l# @" m! W+ l         sum++;}
4 k+ k, w& Y# A" Q# g* C     if(sum==M-1)
( Z/ X: Z' @! Z# q8 _        break;3 c5 n7 L; [0 h6 k0 i
     p=p->next;0 e. s# ^1 K% g
    }
( _- }1 \+ A- B7 K    p=  U" ?2 h. s  ^' q  ?& `$ L, j* h
    head;
# A' S  }" `  p3 D9 s' C    for(i=1;i<=M;i++)
/ {, p& ~& c( g4 r- S. `    { if(p->flag==1)
! j2 k* i4 |3 W( T. ~        printf("\t%d",p->number);
+ A6 y, I4 r' f  j      p=p->next;
$ B' ~* i( O1 c4 p7 F3 @    }
9 Q/ O. m7 t1 ]* I+ {8 S2 B2 R8 S% ^. Z: i% ^# V7 o

$ G% O/ \  S6 |1 D- U
( y, z3 Y( S) X- x) `3 m}
, S/ U2 w7 S2 r& z7 d
第二种方法:数组; p/ }% q3 j( h, ^8 v8 m4 F6 K
#include<stdio.h>
9 m/ O5 H" t' Q; @; ]7 a$ W#define M 85 s/ M* z; f0 ]* p1 p$ o1 P* B$ q* a
struct monkey4 ]0 C0 N* M: D8 E* j
{int number;
% l1 K. a) o- k. X" \5 M* Uint nextp;2 ~% M! v7 r3 E5 h& d% H
}link[M+1];$ l" q+ |2 T8 t. I- s
. Z/ y7 b1 k) O1 y9 ^( z- E* G
void main()( l+ x" R3 a2 l& Y
{int i,count,h;' \$ ~2 Z9 E3 m9 T/ G
for(i=1;i<=M;i++)
8 I: G, u. x8 P+ N{  if(i==M)
7 ]  ]; V2 y2 z% y, j& y4 m   link[i].nextp=1;$ B# s  i/ q( `- Z' A2 _9 X7 h
   else; c( r5 S' I6 b9 Z
   link[i].nextp=i+1;
% x6 b" u8 \$ Z; \$ U0 V4 }  link[i].number=i;: L5 l" X$ ^0 K# X2 P7 z
}% `" n$ M& K! x( ]# H1 @) L
printf("\n");
3 b$ B' b, T& c$ bcount=0;1 M6 {* M/ P, y' w5 d& m  ~
h=M;
- d  P2 ~5 W4 b3 K4 k0 F& uprintf("依次退出的猴子: \n");
; o6 g9 Z+ @; f0 N( z* swhile(count<M-1)2 H) N2 g( M. O6 U* m4 A
{i=0;
2 x% L! S9 F7 ?5 @& g- |/ Dwhile(i!=3)
# V0 c+ |; V+ M{ h=link[h].nextp;6 s) ^+ k0 X! a0 p0 j* P
   if(link[h].number)
2 g% O& S% `) r& Y     i++;}( j' ]% |6 P/ k6 |0 j+ \

, u; L) U( y6 `2 D" O! eprintf("%4d",link[h].number);1 Q7 F) H) @( p$ }
link[h].number=0;
! `4 F: Q+ z$ y. X* C* |: Q# L8 Kcount++;
2 O+ C6 `* Y. F6 r. t3 `  ]  i}
7 ]/ X* p& o9 v
, H; q3 \9 T4 Z" Q0 Wprintf("\n大王是:");
" w! v, s6 c! I: H$ b( l  for(i=1;i<=M;i++)
! A2 J5 d  f! L& |; E& I' p% k  if(link[i].number)
% d* `3 D! k7 [    printf("%3d\n",link[i].number);
! _+ t  `0 d) L
2 H7 }: |; F5 y! P
" t" F/ C  n* l" P  X0 G/ b}
  d: @+ y# s6 w
第三种是普通方法for循环
+ \$ b* X3 Q7 E: M  M
#include<stdio.h>
& w6 O( j; ?" l1 }void main()
# j! I# T% W( l* `$ e{ int i,k,m,n,num[50],q,*p;3 {' }& |- @5 ?# d8 U
    clrscr();
- G( v2 \  I$ Q  z   printf("input number of person: n=");
( ?0 y2 x& o: y3 i8 i" t9 d1 c    scanf("%d",&n);
( x; B4 y8 J# ~' f' \0 F2 t; jprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
. t6 H% p/ m3 E. L& W+ Q    scanf("%d",&q);6 B, e* h9 X4 g% |# r/ ~
   p=num;
  \# x1 F+ n* [% ^. b) A- x  for(i=0;i<n;i++)+ L- i( o. r2 o2 J% v& b% O
    *(p+i)=i+1;+ I9 m5 @0 n7 {9 H2 D
   i=0;; d5 V4 m7 g: m# A' j
   k=0;
' d- Z+ J; z' p) ]   m=0;$ E2 |6 ~2 t0 m! m3 K
  while(m<n-1)
, G0 a5 C- c8 J3 a8 `+ g3 {   {if(*(p+i)!=0) k++;# J9 W* P1 t* z6 n) \( b
     if(k==q): B" w6 z+ C3 f' i& d' A3 i
      { *(p+i)=0;: w. s" R' j6 d" @" a9 b6 x& F& W
        k=0;
3 i8 O0 y3 j8 [1 X        m++;
! [2 d% }- V3 M" n/ x& h" y      }& P1 O$ e4 |+ K; q
    i++;& s3 U0 }2 |4 K7 ]5 e
    if(i==n)i=0;
/ T3 q/ y# f% ~/ E( V& U7 b0 }   }3 e) O- o3 ~& r
  while(*p==0)p++;, W6 A. X; F% h
    printf("The last one is NO:%d\n",*p);
. k" m, D8 I6 C. n# X     getch();
( W% ]+ `* k! k
! a0 O/ i( U# X) l% I$ y9 h}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;" j" G# g6 ]' I; s6 j! g" K+ v
namespace 又费马达又费电
+ `, _/ d' o3 J% ~+ o* l{+ p+ z# @$ {& p  R. C8 T, i
    class Program9 m2 c0 u3 u& d5 ]: i. j! U
    {
4 w8 T9 z# {1 C5 i7 ]) o/ y        static void Main(string[] args): [9 p2 Y) U. {% e: O
        {9 e" i( V  g- q7 b3 ~2 b
            int m, n;; [! O4 K; `" ]* W
            Console.WriteLine("请输入数组长度");  |1 c3 W0 {; @* ], o' B+ W
            m = int.Parse(Console.ReadLine());//m为数组的大小/ }' Y; M- ]3 \" G8 F  D9 \
            Console.WriteLine("请输入要截取数字的大小");
# P: \+ Y  V; i" ]' F- F            n = int.Parse(Console.ReadLine());
- t5 C' C& r3 ^$ \; J* z" Q% q; R            int [] numw=new int& K( @& {# u4 p& D6 |" n/ P
( }8 j% y, w+ R: x6 ^
&shy;&shy;&shy;;
1 N% Y8 o+ j8 ?4 C! ~0 F            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数, u& {/ ]. v  k5 K' d0 S
            {
+ j, h7 S% ?' q5 Y$ L* Z  L" A4 r/ q                numw[j - 1] = j;
/ k# X2 X+ j- c( E( X8 n& Z            }
$ E. \: `/ P  o+ H9 @            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
; T# ^6 ?) H. O( H6 P            while (d != m - 1)$ s- Y' M) t3 i( v
            {
6 r/ K! Y. W1 M) y                if (i == m && d != m - 1), k. U3 Z& [8 Y' a: j" _3 s, S  f$ }
                {
! B& }* v$ m1 X" j% b                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!& T% A* r( c, l2 F1 X/ C
                    continue;
( O  s( N* z8 k2 W7 w+ P9 K. Y9 N                }
+ [1 W9 T  Y2 s% C' E. g# Q                else
4 N  W7 \: L4 ^( m                {! G8 t% d- b: S5 `8 s
                    if (numw[i] != 0)
4 F5 E7 {; G2 X3 _% d' }                    {8 y4 S0 d1 ?% I! `, m- z
                        i++;
) w. w8 V0 X* s! O  _                        k++;: N' J- v7 J9 q% N
                        if (k == n)
& S) @/ l9 v$ \* c' P. D                        {
# P% n3 B7 n" F% B. v                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
( n% O/ x0 i" w$ o$ r9 d( t                            k = 0;
! R' T( B( A/ T# I              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1+ u2 f- i$ R: |. L3 O
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 T0 {. A: [. r7 h+ A                        }
# X: \0 @5 ]( D4 f: C' z) g' ?                        else//输出暂时还没有改变数组元素的值
# u5 _2 Z4 w' O1 T+ S                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);" D# v3 x9 L6 B8 _) b/ B' {
                    }
2 Z  u- D0 e: N                    else) L5 {" f$ F- i( I
                        i++;//数组元素为0,直接跳过,不计数。。。
+ k3 i6 g, L& Q& T                }, g# s, q) }' q! z" o3 h2 G! g* D) a

6 B  D4 ]! e/ h' @8 a6 U
) ^! q# o9 x, J  _            }//结束while循环8 @/ C: Y! ^: i$ w! c, _4 ^/ z
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦+ u* o( W# ~1 S; |
           4 T2 H, t) s: u* i
                if (numw[i] != 0)( l: \; I" f2 D5 V7 A$ G' B
                    Console.WriteLine(numw[i]);1 C) [+ Z% h3 `  v8 h& ?8 {0 W: X
           
# F6 ~1 ~2 ^( a            Console.ReadLine();$ x5 J# y( `; L& N6 }4 t7 `/ X& J
        }9 ]8 C3 n- i" v5 M9 v: |1 \6 z
    }# E2 B# w/ ?: `: F# N) L, @
}
% T3 `0 b0 @, W( O% c1 a" D  y
小甲鱼最新课程 -> 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-3-6 13:30

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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