鱼C论坛

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

猴子问题

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

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

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

x
大家好!# ^7 Q; \2 k$ S" C% n5 a5 c% l. n7 u
这几天我在忙着编一个问题,我用了一种方法编出来!1 \1 N1 q/ C6 F4 l
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!# {9 `% L' T0 i; x9 {7 V& \2 Z
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 - Z" Z/ f% e! H  R/ J
  E$ S$ [9 P( j

0 D7 x. h6 o3 F- P8 S
                            题目; w' z4 p6 ]1 w: e8 T+ Y
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 X5 ?$ o* ]6 n+ F5 X, `第一种方法:利用循环链表
+ N4 y# A8 `1 \1 Q- u3 }; f* e#include<stdio.h>+ b% z6 c6 t  r! L: y
#include<malloc.h>
6 D# X2 @0 g: l* L% [3 b#define M 8            //共有8只猴子: o6 R# l  k1 {+ j. |' A
#define N 3            //数到3只时退出第三只
9 N9 p  I# t: c* Z/ D: u2 }typedef struct monkey4 Z3 o( e9 \8 [
{int number;) e( F6 U$ S+ v7 r, Z
int flag;
, @4 K5 D$ ^7 V, Y/ sstruct monkey* next;
2 [* P/ T4 R8 V}MONKEY;8 ]0 b1 K$ l6 K' J1 X- z! G
main()
) G) K+ v' m- b6 [' R{ MONKEY *head=NULL,*p,*s;- N+ k) J4 w6 j/ @) I
  int i,sum=0,count=0;
7 ~8 b6 I+ k- L$ L( ~% Y  clrscr();              //清屏
( v0 @$ L1 Z; v+ r- ]  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存1 G5 O$ O' ], f  e; q4 U5 ?3 }3 F
  p->number=1;p->flag=1;
) _% g2 v! L2 g  H  p->next=head;
; S! K. `" M' K0 P/ v2 v  head=p;
1 F/ Q; f3 a6 x/ a  for(i=2;i<=M;i++)
& U: t1 k: ^6 C# e    { s=(MONKEY *)malloc(sizeof(MONKEY));, n' j% g6 H. ~
     s->number=i;s->flag=1;. V9 w% k# e9 k$ Z
     s->next=head;
) B; x: t2 V* P, ^; G7 D0 j5 {( p; |     p->next=s;p=p->next;1 G5 v6 _9 B' Y: g' G
    }
, h) S, \1 B) @6 g# [    p=head;) @) t0 H/ {. \: U" K) {2 @! J$ ?5 q! @
   for(;;)
6 {) y( h( b2 J$ v0 s/ Q$ Q    {if(p->flag==1)
* b( g& C' R1 K5 d       count++;
/ ^& ^' |( l" X% C     if(count==N)2 Z; T' I2 c. C' i7 A2 `; p: o
        {p->flag=0;
- t2 \& r  n( e) G" U0 C# W- V# W1 s         count=0;
6 ~7 ^) B  y6 U3 w, W; Y1 _         sum++;}3 u2 y# D4 g- }, \: T- T0 f
     if(sum==M-1)
+ U* c$ j$ H" h6 p% o/ V& T        break;
; [" Z' c- B$ |! {. u     p=p->next;
5 z& h. K) m0 b2 {    }
+ C" l2 n0 s$ T! T( W  ?; r$ H    p=* J! X& o1 [+ u
    head;8 X7 Y: o- r0 O
    for(i=1;i<=M;i++)' A, v% U( P) i7 w7 g" R% G7 H
    { if(p->flag==1)
. e4 J3 [4 R# K8 B& \% R8 p- J, o        printf("\t%d",p->number);
! l$ O; M, B+ `0 b      p=p->next;
+ I5 K+ h' N0 T) a$ S4 {8 |    }
4 _- T! y0 G+ q6 S9 f6 ]" V/ @0 g$ W- t5 x* ^
9 u' m7 i4 @! W8 b! |" ^7 q
3 f1 G3 ~5 t+ T$ d$ X
}

; @5 T9 N7 A; z4 p第二种方法:数组
& @# K" s  P3 U7 _8 x#include<stdio.h>- k: w; Q9 z  F3 e) f
#define M 86 Y! M7 ~9 \+ g& r# F0 i
struct monkey
! ?, t  f$ u8 h# h9 l6 k{int number;
) I! `9 ?. I1 d) Y0 Q! F2 tint nextp;
- ?6 X+ T" D0 x) ?. r}link[M+1];
* l0 S! h6 C/ |9 }
' x, o& B  c; ?) K/ @& @% N( B8 uvoid main()
1 q, R# m( X5 \{int i,count,h;
0 C  U6 {# }' K) O: w+ g, Pfor(i=1;i<=M;i++)0 c# |+ g; F/ u, }9 ?
{  if(i==M)
3 N4 C; `1 f# Q! Q+ i' j9 }- c- K   link[i].nextp=1;' U' I+ m9 u6 i. l# |. z
   else1 b7 ~" b6 B/ `/ P" c( L
   link[i].nextp=i+1;+ u4 @8 L; S* s- o; {' s4 o2 h/ \7 j4 S
  link[i].number=i;
; J" C; c" E' U3 O9 B0 m5 P}( g9 Z- P, D8 f+ \3 T7 R
printf("\n");
+ B$ E7 u* C* \/ c, Dcount=0;' g' |) A- S6 d: i2 f# x- ^2 Q
h=M;9 o# ?* n7 c4 A1 e+ F1 L& A$ P
printf("依次退出的猴子: \n");8 E6 S% h$ w" o0 t
while(count<M-1)
3 d" w7 ~% k+ w8 ]{i=0;
* {2 b( i4 H/ F8 [5 j- Uwhile(i!=3); `" o2 [$ e0 f) t% ~
{ h=link[h].nextp;8 E! G+ i. R. N  I) H
   if(link[h].number)
& J: r# O' V  f, Y     i++;}
: P; K& @! h: k$ Z
% r5 ?5 G% p2 g+ Vprintf("%4d",link[h].number);
% t& u3 k9 w( U4 Nlink[h].number=0;. R( t+ p" D# D
count++;
& N- N' j$ u- T' M; ~2 u/ ?: U( t}
* e0 w- t8 J& }4 Q
9 W' B' k1 ~+ Q6 Cprintf("\n大王是:");& v* J# G* E1 U8 [
  for(i=1;i<=M;i++)
" b( i, v1 n( P& c* D& t' H2 F  if(link[i].number)
  Q7 h* G7 V2 R* E, O    printf("%3d\n",link[i].number);5 D- [$ c$ \9 y* H  |
! X% [& C% Q+ E8 {, H4 h

; ~  x+ V$ L! n  ]1 m}
  ^5 d4 b5 E% j" w- A
第三种是普通方法for循环

  Q8 }1 Y0 _9 M#include<stdio.h>. }% E, c) Z2 T  H0 y3 O" I
void main()
$ Q+ G. c& q1 r3 ?+ s( i{ int i,k,m,n,num[50],q,*p;' `& n; `1 T4 {
    clrscr();
% D" A7 h3 p6 |0 G   printf("input number of person: n=");
4 s6 `2 `. K, @2 J' ?    scanf("%d",&n);( u' A+ M: p0 Q# f$ {# g
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* p4 n) z( i7 Y
    scanf("%d",&q);
6 U3 b$ Z' c. S3 v; P   p=num;
+ C/ i, [" W! x  a) n) y  for(i=0;i<n;i++)
! j( ]$ K7 d( o    *(p+i)=i+1;5 C' S3 V  {' x6 w- S9 B+ o( P
   i=0;0 ^; [' u( s+ ~7 S: Y6 Y
   k=0;
7 T+ |) h9 m; B# Z0 J; |: g   m=0;8 K7 p/ F6 `+ r: [
  while(m<n-1)5 W1 E8 ]; [# T0 T0 [
   {if(*(p+i)!=0) k++;
2 s5 {: }" p3 B& p     if(k==q)7 p5 G3 t$ e6 Y/ o1 R' @7 x$ r8 s8 ?: w
      { *(p+i)=0;
2 [- G0 `7 J7 k        k=0;
6 v2 Z4 L' A0 D9 H2 v3 F9 S: E6 L        m++;
) y% I, P; }0 q: w7 ^      }
% u% @1 a( a7 N0 w+ j    i++;
* e& _3 \! o0 A    if(i==n)i=0;
! V# _% A* }4 z0 G   }( C  I# K6 R6 L3 W0 P: d/ y
  while(*p==0)p++;
0 y. f3 t: t' b/ `) r    printf("The last one is NO:%d\n",*p);
* b0 S* Z5 s  [. }. R; u     getch();
2 y$ _4 S# i5 M& @! x& Q4 R! n$ g" F0 g2 X
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;& J+ K+ B2 W: Q% B
namespace 又费马达又费电
: f3 s* ?  O! s% P0 r{( }. h  x4 y5 C$ y& Q0 G9 v1 b0 m* Q
    class Program9 B. L0 {$ b" W7 }0 t: S
    {
0 r# `! W( b  \5 |  X        static void Main(string[] args)
. k" J# K7 W4 N" `: O+ l; ]% l/ s8 G        {
9 T. ^7 ?7 Q7 m4 i            int m, n;( |/ F+ i) w& ^
            Console.WriteLine("请输入数组长度");
! _  M6 ~, g* l; P, H1 E            m = int.Parse(Console.ReadLine());//m为数组的大小
1 Z5 c7 y: g3 I/ w8 Y* _; b            Console.WriteLine("请输入要截取数字的大小");: N9 i5 b6 e5 o0 R" A/ u6 f  d
            n = int.Parse(Console.ReadLine());
! Y' \5 i/ ^* i6 k            int [] numw=new int
! x7 O! I  ~" V4 G# Y" t& `0 y' S% j! \
&shy;&shy;&shy;;
1 G2 _9 l2 z. z; I  ]% z* Y( \            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数# i4 [+ m" R) e1 \  ?
            {
  l! A7 j6 A+ n8 p0 v                numw[j - 1] = j;
4 g7 [1 M: S4 \, p            }; q) R7 |, l, v+ Q1 p# T3 g
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
! w! A6 X7 u# d5 y+ O            while (d != m - 1)0 a; \* x' A+ h% ]  S4 g- x1 K
            {0 `9 F2 f9 a9 ]. j* ]. H
                if (i == m && d != m - 1)
8 a9 |6 W+ \3 n! S8 A                {
' g+ ^1 P4 t2 t5 N- o                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
3 I) b% y! C& `& I7 `; d8 n                    continue;
( f. C/ y3 ^  e) ~) U0 \                }
  u3 b2 z0 U# Q& B# y& s( J                else
( a- A2 k9 E3 T; `8 t                {
5 ^& _5 k6 j' }; {                    if (numw[i] != 0)- `* f) m4 E1 D
                    {
8 ^, a% R& \6 C; L                        i++;  q& p9 g1 R2 f' i7 V2 ]
                        k++;
  @; `/ T' Z& p& R' {6 o                        if (k == n)
: \  D, l) E! ^9 X2 L3 k& H                        {
0 f8 E& M% z9 y# v1 x: `$ h                            numw[i - 1] = 0;//把在n位置数组元素的值改变了& r' {9 X. C7 e# S6 Y0 q
                            k = 0;& r/ E6 ?* J* H
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
7 K, u% C. x% q3 f2 R  ]                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# D% k- h6 P% i                        }8 V( Y4 j- x% ~# u. T" Z+ E
                        else//输出暂时还没有改变数组元素的值, u8 e: e! d) a2 H
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
1 ~/ w& V1 @$ u/ _                    }
' O& v4 _+ B" }+ H% r) g' ^4 U                    else8 [) C6 [6 o9 d0 O
                        i++;//数组元素为0,直接跳过,不计数。。。
+ A  ]4 X: r  |                }
9 g' i, j% e: Y+ J4 O, f$ C# V 5 k" r; S# W) s
7 c; O+ U3 ?* Y) a
            }//结束while循环0 `# n7 @5 r: P$ C' H: ]
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; P, }! \) p9 v6 h
           
- m1 f- f  g$ W                if (numw[i] != 0)6 W- `, |( {8 H, X- w
                    Console.WriteLine(numw[i]);. ?+ x4 h! Q8 d. ~
           
& T0 i; }3 Z- r5 S: ^            Console.ReadLine();2 s9 F9 @4 n- ^- Y1 |. t
        }
* t  ]) i. Q# h; a' I& T    }4 Y+ G1 b4 \( \- Y: M* n" M
}& G4 M/ g4 U. R; T9 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-6-24 23:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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