鱼C论坛

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

猴子问题

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

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

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

x
大家好!
# T) |- o7 ~( W8 |: h这几天我在忙着编一个问题,我用了一种方法编出来!
/ _2 b! c( p3 U6 m但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!4 V  H) i% [/ @& n1 g4 I
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
1 w! A3 \/ Z" C/ J3 R+ @1 L9 ]" J
) I! Y8 `4 `% q1 w# P
% A4 |/ P3 P/ p, _' `: J/ f. G9 w% i
                            题目
4 s( A  S2 R3 v/ s, ?山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
4 i  M) R% A0 J6 F7 t第一种方法:利用循环链表
. u7 o3 g* x" e4 O5 ]- j* R, J#include<stdio.h>
" l& ]& ^+ e$ G; m. J3 b#include<malloc.h>
- t: z3 V6 Q* ^2 H; r" k#define M 8            //共有8只猴子
' X/ l/ r1 n9 b#define N 3            //数到3只时退出第三只# T" B) b: }% i/ Y& f  ]+ |5 E
typedef struct monkey/ D! Z5 C) C0 |9 E4 i" d
{int number;
; E; O% i/ Y5 i1 dint flag;
% O) z. X# h3 _6 O( R+ K: Ustruct monkey* next;" s5 r) e! q/ S& O
}MONKEY;- |" s' P1 f, Z4 H5 u; t* ^
main()
5 P- U- v4 ?% B: o{ MONKEY *head=NULL,*p,*s;
8 }* c8 K0 ~/ `1 D5 n: r  int i,sum=0,count=0;
2 I6 G$ f5 d2 `  clrscr();              //清屏
: a" ~9 N! v2 G  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存/ P0 G4 c. ~) t* k$ B. L, B& s0 i. b
  p->number=1;p->flag=1;8 F+ d2 N" M$ @
  p->next=head;
2 ?3 ~: f. J2 D% A" s/ \  B  head=p;  q9 L4 H7 k% n0 \7 m
  for(i=2;i<=M;i++), ]4 Y4 e1 W% u' U0 G8 P. ~& f" C% t
    { s=(MONKEY *)malloc(sizeof(MONKEY));
" O. L& @/ h2 J0 ?) h9 M  c2 T! A     s->number=i;s->flag=1;  u5 l! F8 _8 t( F4 d% l
     s->next=head;
& R2 T. S% M. p4 _8 j! d6 l     p->next=s;p=p->next;' C& |0 j2 s; k, x% q5 W
    }! O1 M" ^' R1 Y* p6 `/ m
    p=head;
2 y% V* F8 T+ c, j9 x% [   for(;;)
# r# M. V4 F1 o, A) W/ X, _    {if(p->flag==1)2 p/ X/ Y; M7 ?+ L6 r7 O) g0 e8 ]* I, m
       count++;
* h) {* z9 x& D$ T4 O' ~. R5 T     if(count==N)- H! P8 x' }  o' i% a
        {p->flag=0;& ~! E6 c; f5 D- P$ t0 z( M
         count=0;
5 ?( w! l; j1 u0 I         sum++;}
& D0 @! u" K0 d) j( D! p* _     if(sum==M-1)
% v6 T/ F% C% V$ o6 b/ f. O' d3 p        break;, v. W# _/ I: Q' s2 f; j# I3 I0 \
     p=p->next;
2 k5 N) u( n6 i    }
; H& F+ N# k% V! b& [4 l' A    p=
/ ^+ g# d: k  i. F1 Q+ s" Q    head;
. Q+ y( C7 g% W* X- H    for(i=1;i<=M;i++)
% a- y( {5 _! g. j; z    { if(p->flag==1)4 D/ v/ d/ k5 t" r5 n
        printf("\t%d",p->number);! _/ q2 E, T3 y4 p/ @% \
      p=p->next;
. d5 r+ R6 B) G: ^  g+ f9 ~7 d) X    }. I4 K) H5 b" f. V, u* M; [8 x( B. t

1 ?' E! M. y% u8 t4 N& M* N
+ ^& {9 u# E( W
, Z! J, E4 F$ D5 N8 \8 E% k}
" d% q" [; N$ s* e$ C0 o# U
第二种方法:数组6 l: t) E# t9 u- |7 p$ X- X; `+ m
#include<stdio.h>& ^8 l. v6 S+ A/ S! C- v% G8 v
#define M 8
! k% L5 B3 _$ ^- j8 pstruct monkey+ m9 c; b7 l3 G- r
{int number;
0 g* s- s$ }; R* e$ Y; @# {' V% _int nextp;
( A/ \: A# V2 C0 ?2 i' K}link[M+1];( ?5 \) S. n; a" l
9 h3 `$ h6 R- p; ^8 v$ W
void main()
0 Y9 \6 [: D. Z/ ~{int i,count,h;
( U+ \2 T7 a, y& Wfor(i=1;i<=M;i++)
# u* V5 Z" Y* S8 V6 q/ I/ q$ ^{  if(i==M)
. F+ e& @7 r4 w   link[i].nextp=1;$ z# f; z  Q: D7 v6 e& j
   else
2 ]& D6 T* G8 T5 B$ ~: t$ Y   link[i].nextp=i+1;' z; N2 h! |3 C- L# G: W
  link[i].number=i;
6 G3 T* ]! Y' d% ?}
$ q/ t6 j0 x: I" Jprintf("\n");4 r" D7 L0 V8 K
count=0;
8 u2 F9 |, J3 S1 _4 r+ r% Vh=M;
9 S! N- F1 c7 k( ?: Gprintf("依次退出的猴子: \n");
* W, O6 L- E5 j: a3 S* N# p, Gwhile(count<M-1)
* r  G, O7 b) @: s{i=0;+ ~8 [9 X; y: D9 G
while(i!=3)
5 ]9 }- c0 \) W' P- K$ H{ h=link[h].nextp;  Y" n0 c) S5 m, }! L0 e
   if(link[h].number)
( Z: \- z! ~0 l4 `1 P+ U9 r% l     i++;}! Q1 E7 r7 k" J7 {
' J% E3 P4 k/ ]! F# H  t
printf("%4d",link[h].number);" w* f6 k5 r$ h+ f. Z2 @
link[h].number=0;
% n& d0 U2 ~9 X" p/ mcount++;
3 z; `' M# D. i: O}
4 o& w) N4 L& s* R' q
( P6 D2 ~+ B0 I7 a$ z3 U. Q. Rprintf("\n大王是:");
6 C& s7 x+ E  ?/ {  for(i=1;i<=M;i++)" S$ i- X/ |: u% h
  if(link[i].number)
4 Y) V1 K1 n* s0 ~! R    printf("%3d\n",link[i].number);) g0 @( c( Z, W+ ?
( g  I8 u# C$ U2 O4 i7 P, L
6 A$ M/ m) }" e0 |. I1 K+ X
}

6 k: d  q5 U& _0 k1 L第三种是普通方法for循环
! P" R4 \8 }; w( |- s3 E
#include<stdio.h>
( @- s3 v& u. W$ M5 m1 z0 Svoid main()
, t6 _8 Q- w5 E" i% E{ int i,k,m,n,num[50],q,*p;
+ l+ R' k4 G2 {% z    clrscr();
1 m" C% m& K# A   printf("input number of person: n=");
: d+ \% F4 a8 x3 X+ b, `    scanf("%d",&n);# _9 ?+ l% R3 B# _* S) X
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只2 M, U  |0 x8 a* F1 |8 ~6 j% B
    scanf("%d",&q);
  C+ w) r8 W, h  @   p=num;$ m. w; _9 Z, Y% r7 o  H; B  F# N
  for(i=0;i<n;i++)4 [! V7 Z% A7 a2 h" k& `
    *(p+i)=i+1;' X9 U2 G: X2 Z4 c
   i=0;$ J. [! }' Y7 q- S
   k=0;" v  ]2 @4 G0 G. e# y& s; N
   m=0;7 L" J* D( q# L# B
  while(m<n-1)  \+ r( Q( K1 K+ D6 ]
   {if(*(p+i)!=0) k++;. Y+ v+ m0 U; m4 k2 `' q1 R
     if(k==q)0 W9 B+ E1 g! I; Y& B
      { *(p+i)=0;. Q+ f  f6 t( r: O$ z: |: k/ E" e4 h0 C
        k=0;
8 s) k/ _4 E: a, ^0 c6 }- V        m++;6 ?6 M, {' y+ l) t0 @
      }
3 z1 p. S, M# B! f; |) R    i++;
# R" a9 i* X" v* C5 @    if(i==n)i=0;) D. e, W  M! \: }; w  J
   }
, Q' ^' u& a- I  while(*p==0)p++;- ^0 \& g, U& l! a8 D' G
    printf("The last one is NO:%d\n",*p);
" y$ |9 ]9 x- e- M# d( T8 n' [     getch();+ W0 `( ]. h) H- F
- X6 l4 C  z" H
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 y& D) I; ^4 J
namespace 又费马达又费电
) S! V3 Q: P+ t" d; w' g{
9 v" V; u* p4 @- w; S) o! W4 j    class Program
* s2 w  H  o$ v: q. I9 ?% E    {' }2 O4 H, C' Q" o6 B
        static void Main(string[] args)
3 E1 r  w, [9 Y* w+ F" p        {# t, {# K: ?8 t2 d, z
            int m, n;
  w' Q2 r, I  n6 @; M' O            Console.WriteLine("请输入数组长度");
) I6 C" `& u/ d, f3 F            m = int.Parse(Console.ReadLine());//m为数组的大小4 L3 s7 F! T# F6 O3 H% m7 h; ?6 O' ~
            Console.WriteLine("请输入要截取数字的大小");1 w( K1 R) D+ L+ M5 I( @
            n = int.Parse(Console.ReadLine());
) S0 K2 D3 F, q5 w6 ]9 q            int [] numw=new int/ _% r1 {; y+ u/ i( h

; N2 f3 @) H7 V% ]9 n; l6 @1 M&shy;&shy;&shy;;
7 s$ \& Y3 l- f8 f$ _0 h            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数7 S% Z& e" m* h$ O
            {
, I+ t$ [+ p$ o! \. O5 R4 g' K                numw[j - 1] = j;& f& D+ A2 H! [3 r
            }- d2 K+ w* K$ p" N* N) Q4 o
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!% m$ w6 G" p: c8 @# Y7 G5 z6 N
            while (d != m - 1)
- S& A5 i4 K( y; d! k1 I            {2 {( q0 S2 R/ l. r$ }9 ^
                if (i == m && d != m - 1)
% ]$ ~' a! p9 b/ _' h                {
8 ?9 T( j% f/ j- ]                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!) d, y/ ^* |( w4 s- Z- d! f, e
                    continue;
, i9 `4 U5 `+ J1 C7 L3 ?                }0 q9 _, \' V- U+ f* k
                else
# @' w- H0 T& }9 ]                {# b: c& V1 {' n/ S9 H
                    if (numw[i] != 0): y3 M. ~2 r( M# A: @7 U- ~
                    {
1 ?& F5 u9 k2 e$ ^                        i++;
% B3 T- \9 Z% q6 V( J                        k++;
$ ]: N" z/ @3 K- o' ?/ U                        if (k == n)" f: Y7 A6 D" l3 J& F
                        {
( ~! u9 W7 H8 `7 V" U& |. p( H2 |  k                            numw[i - 1] = 0;//把在n位置数组元素的值改变了4 \" f, d" d' M; y7 `: `% T
                            k = 0;
/ G8 u( ]. E: u2 F! p8 e6 D              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1+ @; e: w) d; t% j8 g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* Q  Y) ?% V* M7 j
                        }
& Q" \! l: ?. J                        else//输出暂时还没有改变数组元素的值" T: s2 Y3 R: r: }( L6 N4 t
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 M9 G& j6 O& u% G- T1 q
                    }
9 O, ~" z" W. X                    else+ ?4 ~4 a9 ?" k/ w
                        i++;//数组元素为0,直接跳过,不计数。。。
& {% ~' N* a: h7 }7 P; i                }
: u/ I2 S% i( o/ E
# K# w. Q* h3 F. G! [5 }; Q7 t1 X2 K& x
            }//结束while循环& o+ {' N2 ~# l8 ]. [7 q
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, E; v+ e7 ~% R" c           0 w1 B$ U2 _4 O. g* Y
                if (numw[i] != 0)! f4 |6 @/ G! ^
                    Console.WriteLine(numw[i]);
6 g1 Z( b  `9 u           
/ O; z! Q4 [/ K0 A6 R6 v# U: F            Console.ReadLine();$ s/ q1 L) d- J. Q& D  ~! R6 r
        }
% A2 \- j' @9 `0 U! \    }
. E& H1 C0 w- j' n1 V6 Q4 Z}: e0 f/ C! s0 V7 y+ _: Z; ^
小甲鱼最新课程 -> 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-2-13 07:28

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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