鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' `9 Q- N2 B" v* W/ R- g: x1 D" M这几天我在忙着编一个问题,我用了一种方法编出来!1 m' [" K' \/ p0 g& D0 Z9 U
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
. D" [9 `7 Q4 W; ^6 i# t  S* Z9 {注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
) d1 J/ d0 T% U- Y' C  z9 H, ?! t+ }4 _7 h2 R3 G' i3 @
$ u3 N( u+ H. f! w, t; u) G+ ?' D1 a
                            题目
! S* J  `7 @6 J山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
4 H  _/ ]. r1 P- o, ?第一种方法:利用循环链表
( H6 a- ~5 ]! Q#include<stdio.h>' ]; o3 `2 H. u
#include<malloc.h>5 V# B+ i& m/ H* _# N, Z
#define M 8            //共有8只猴子
! Q  t/ A$ x) {; B9 e#define N 3            //数到3只时退出第三只9 T& i5 {2 u2 Q/ O1 Y7 o
typedef struct monkey
( J5 U8 [8 b- l# P8 G{int number;  ^7 e0 `4 W3 _3 x- N/ H' @, Z
int flag;
7 J7 f: M" l, Rstruct monkey* next;3 \' J3 D! W* \0 g7 s
}MONKEY;
6 f2 f" ]; Q9 K( n3 }main()
: ~8 B! y; I. _; g2 B{ MONKEY *head=NULL,*p,*s;
+ n: h/ \+ G7 o0 m  int i,sum=0,count=0;
# o+ k$ l% r* Z% A& b  clrscr();              //清屏
& G- N" O8 a" ~, ?& U  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
. G; S: \' ?4 p  p->number=1;p->flag=1;/ u! U5 B. E6 h3 b
  p->next=head;
# |2 z. V4 m* |2 ~  head=p;
# ]# X9 C% f/ Y. v4 b. d  for(i=2;i<=M;i++)
( W1 I2 W$ _) `2 T  n) Y    { s=(MONKEY *)malloc(sizeof(MONKEY));% @, x( V' r4 j5 T0 H
     s->number=i;s->flag=1;# b& g/ K+ A, O/ ~9 |" t! N8 g+ b, z
     s->next=head;: V5 Q- L( s0 J. G6 \. m  U
     p->next=s;p=p->next;
: C/ `, h  h3 B5 R! {! U. j, z- ?* W    }* S" d, {+ C4 a  @- \$ f0 n! A0 E
    p=head;2 Z& Y, {, Y4 Q9 p& y
   for(;;)0 @: h! R% q2 l; ]
    {if(p->flag==1)
6 s* h( s- o5 v6 i  a2 ^       count++;$ g! u; T0 T+ y' o: o1 {
     if(count==N)
6 d, i8 s3 ?3 @" i1 k& ]* h        {p->flag=0;' I! X3 V6 y% S/ o$ V; E" t! ^
         count=0;
' U2 z0 }0 i2 N         sum++;}; t6 N' v1 I7 w
     if(sum==M-1)" ?4 ]+ _0 P$ L: p- |
        break;
; D5 d9 n; G# u6 E' I% D% h+ L: h     p=p->next;
! {/ F6 ]5 [7 {0 a8 q3 c% i& p    }9 A: Y/ D/ I7 X& Z9 V5 @+ d
    p=2 V  `; ?* N' |4 _  w
    head;
5 g- z# l/ G) b& ^    for(i=1;i<=M;i++)9 u3 N  g+ g" f9 R
    { if(p->flag==1)* c& C2 _& f' g" ]9 E( n% k
        printf("\t%d",p->number);9 D8 M, p/ h# Y1 |
      p=p->next;, F8 j% f% S* Z% G# z
    }
2 `! a( A& ~: U& ~4 ]) p. q% X& {. n  v* a& r

! q! s& n3 P* `' u- m3 i. q
( J  V) E- f, S  `  ~}

# l) p& s, k  n1 z3 `$ m$ d第二种方法:数组& f0 c+ @0 Q* k# u
#include<stdio.h>
" w/ A* v, h" I. @#define M 8
2 h1 E# r6 \9 r8 fstruct monkey
* g9 r& X0 \2 `{int number;: U3 i* P4 H! E
int nextp;2 Z0 D+ M3 u2 c& J/ f
}link[M+1];
/ c1 D: q( U' y" ]; Q' d1 @1 J: w7 L6 W  _6 ]- W
void main()
6 b& k. r' R, m9 p3 E{int i,count,h;
$ G4 F* e# A/ o( z3 q! g5 {8 a; mfor(i=1;i<=M;i++)
! |) o- ~" h7 @5 e- y, K+ Y{  if(i==M)! \* R& k! L5 B( @  O
   link[i].nextp=1;( X# d4 r* o. [6 j) w8 l' m
   else
2 p: F5 h7 o4 C4 K   link[i].nextp=i+1;
. g% ?2 _* Q4 Z2 G1 I: m: J  link[i].number=i;5 c" r6 F; k7 Q" E* X
}1 ?+ T; D9 u7 u; ]; _5 q( a& U
printf("\n");; d: C. A$ U3 O2 a4 e
count=0;
( m8 A# q8 R- }h=M;
% x* @; z. J, S! v3 Vprintf("依次退出的猴子: \n");
1 j2 n9 R8 f0 f7 \0 y2 uwhile(count<M-1)" Z0 O" X1 I% A) W" u# A6 l
{i=0;
/ h% ~, \# X1 O" h& T/ s0 owhile(i!=3)
" y8 c# h* H: y{ h=link[h].nextp;3 [" C" K+ |+ T* m9 C  E
   if(link[h].number)
1 u% q0 ]9 p  K- @2 P7 K     i++;}5 }8 ]* @/ [8 Q4 j2 X* k

! p$ |5 j% c6 l" l* a4 Dprintf("%4d",link[h].number);- z# d# M2 m# C) {, P) g
link[h].number=0;
- e/ |9 t% [2 C% p; e% Fcount++;
# u+ ^# {+ X2 |+ W) n/ C}
: C: r# v9 l  j0 O
8 ?+ n, x, q, G: Rprintf("\n大王是:");/ Z7 ^% F! z, w
  for(i=1;i<=M;i++)/ S# m% g/ j: y) H' g- w
  if(link[i].number)1 {* b. M" o4 J8 |; r
    printf("%3d\n",link[i].number);$ }/ }( L  Z5 m: n( O2 Q
  l2 [7 E' I7 n: D
7 X" C+ J& g) P* s
}
( ?4 ]- g+ j5 |/ e& l0 ?) U
第三种是普通方法for循环
$ v: r( Q9 \) D
#include<stdio.h>
# l, y  _  k0 ]3 jvoid main()
* d  `% O3 f$ K* c5 W$ Y{ int i,k,m,n,num[50],q,*p;
/ X, R7 n0 C8 G; }- p0 z    clrscr();8 y) f) o' u% R) V9 I/ {
   printf("input number of person: n=");
5 d* G; B! X/ S" r; E5 V    scanf("%d",&n);& S0 N' p# N- |$ p' w1 q3 ~
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
" h3 P& q' W! K  \2 O4 O5 E    scanf("%d",&q);* l1 q1 D1 u/ P2 A1 ^, n. r
   p=num;
% P4 E: b6 o4 a8 g$ r0 i  for(i=0;i<n;i++)
  c) f, X( K# K0 U5 G& a    *(p+i)=i+1;
7 s* g; n3 f% }2 t   i=0;8 B3 i( v. g7 N; ^+ Z+ I
   k=0;) Y8 t1 m% s# m  A/ [& a" y. H
   m=0;% x% |7 I% k3 e) c4 Y% V  M
  while(m<n-1)" C  y; q3 X, p9 o  {
   {if(*(p+i)!=0) k++;
0 i/ n( n6 x4 y2 p     if(k==q)
3 V. q7 R% p* F      { *(p+i)=0;, T5 J, c* L& j; r1 `
        k=0;
! R, v' `; v. ?        m++;
$ N0 q& A  C# ]" m6 ~+ K3 k+ N      }9 s/ d+ P: _  h) R* I$ I
    i++;
  \1 Q* X1 v' p6 {( B    if(i==n)i=0;
- d. Z3 p9 }/ t0 C9 @7 ?   }& r$ V7 {1 L( H# l  H7 o6 f& M
  while(*p==0)p++;
4 ?7 r! X' A# N# R    printf("The last one is NO:%d\n",*p);
$ P2 Y; h7 c! R8 r% k     getch();8 L: q: R* W% i3 b- ?% E
( o6 p4 R. u& z2 w( M8 c9 R
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;0 {* Z, s8 q- a: S
namespace 又费马达又费电0 Y% J) e7 g6 d, V# R
{0 B3 m& F* P% [( p( K  z
    class Program4 u/ A5 `+ y) B/ C# w& e1 _; o
    {# j5 B0 R. J4 p
        static void Main(string[] args)( k. H- s  Y6 L5 Q7 L2 x1 L, v
        {
1 E$ k- ~, I% V) R$ u; g            int m, n;
* {/ E  i0 w) t% `, u( z5 W  |            Console.WriteLine("请输入数组长度");4 I: H8 O! b' e& w6 d
            m = int.Parse(Console.ReadLine());//m为数组的大小9 ], L+ \7 l- G" [: A  d
            Console.WriteLine("请输入要截取数字的大小");; t5 T7 K4 W2 Y. B, |( p5 U
            n = int.Parse(Console.ReadLine());
6 H* L" s5 F% a/ \9 j% h            int [] numw=new int' x) M8 a" x6 l8 J. L5 b
7 u$ u- j; h, _8 w
&shy;&shy;&shy;;  W/ P& c' ?- J
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数- ?  t" l; b4 i" C
            {
7 j4 T  Q# V8 \6 o                numw[j - 1] = j;
: I9 H/ Z1 J* A6 y6 H1 S( E' n  k            }
" C! }' M" c; R* O            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!1 f# M& v9 J, [' v. Z& C' R9 [
            while (d != m - 1), u! w* K+ R5 K3 ^7 _8 S4 p3 G
            {
% V( Q( i) X, _' D) }. Q9 p                if (i == m && d != m - 1)
. |; ?: s: b3 V* C( \                {- K/ H+ b$ j# i- l1 x
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!# o; D# y# C( O+ m2 a
                    continue;
; t9 j  x8 y8 {! g! Z9 d6 V# K+ x                }
% I9 v7 A- W, [( Y3 p, c: F6 u2 ^                else7 X4 w7 k& \5 H
                {
7 z5 d6 t( U6 g- |8 z* C  ]# P                    if (numw[i] != 0). q0 ?% j( q' S% p4 {
                    {
+ a# K# U5 j/ \& ?9 a$ w' j; p7 g                        i++;
. O- J9 u# e2 {  y+ ?) s" [, Q                        k++;8 H: x- G5 \3 h6 q) V
                        if (k == n)9 T) n$ w- g; D  @( }0 f  G
                        {7 e- `  r: d: x  Q4 ~: w% }- J2 W
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
7 O7 z) X; D# z3 H( }                            k = 0;7 O3 U, s) |9 Y
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
+ n4 k% k+ }# v9 f, D3 n                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: d* V" N) E$ \5 C
                        }
# E2 _! c) h7 {                        else//输出暂时还没有改变数组元素的值) U$ q  ]2 A! ^# D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 x" s$ U4 A+ w: |                    }
/ f% Y! d9 R. A, |                    else
$ \5 L3 X, i. ^) s                        i++;//数组元素为0,直接跳过,不计数。。。# l' m5 R9 x* R# A7 k- D
                }0 y* k4 P2 z  u+ K9 o4 y  W1 h
$ j! b  ~0 K& \& U5 L1 v; f
1 w) Y' H# K4 b& t
            }//结束while循环1 i1 X% P1 X5 }$ M: W" }- y
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦& I* l/ M  P9 ]! h
           
/ F4 N- b- [  y& \0 @! n9 }# C                if (numw[i] != 0)
# B# s8 N1 Y% _1 n                    Console.WriteLine(numw[i]);1 F( _, M( J* e8 [/ g6 S8 k
           
" }/ n- G0 P. q% F3 J  X, }            Console.ReadLine();" O/ ^( m3 V2 }9 Z( m+ y. c8 I( V
        }
8 f( @* a' p3 `9 X4 z/ ?    }' A; k: d2 R/ W2 ]
}& H2 p/ z$ q: O3 t. o" R4 o0 w
小甲鱼最新课程 -> 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-4-21 08:11

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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