鱼C论坛

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

猴子问题

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

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

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

x
大家好!
' O4 H5 t3 Z5 i' r+ ?" r; j" }2 h这几天我在忙着编一个问题,我用了一种方法编出来!
, \+ i! g5 A  x/ `$ ^& L% c但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
0 s: x( q; z3 N7 v注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 9 l( z3 p" S. |6 j8 ~. U+ h
: Q& X2 i; u8 j" E7 f0 S
3 u. L( t( J. t7 M# P" B8 P0 ^
                            题目
* |$ }8 R# r5 V7 d* v山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。& H. F9 C8 {2 O. Z! ?' P
第一种方法:利用循环链表% Q6 v& D* `3 n7 R. Z- T' S
#include<stdio.h>
3 O8 Z1 X/ n% p2 t# J2 [9 I#include<malloc.h>5 }. A# U- q2 n4 s' l7 f
#define M 8            //共有8只猴子6 w. S. x! s2 n) o! T2 d' \
#define N 3            //数到3只时退出第三只; c1 X* x6 t; m
typedef struct monkey
, m5 {3 y0 g( Y{int number;
: x8 i% J9 M; Q9 c, o5 Kint flag;
6 X3 O! T1 U+ e$ u2 }" F& i# lstruct monkey* next;8 }9 F- K7 T. y% E- f% O
}MONKEY;
$ n4 P- I# _8 I4 Nmain()! B5 N- N9 j+ r7 _4 n4 u  R' U$ c
{ MONKEY *head=NULL,*p,*s;
( @( L5 F* d0 t0 S$ u3 o( K) g  int i,sum=0,count=0;* W' O: ^6 k  a+ U5 i# b" J
  clrscr();              //清屏
/ P& ~- h! z1 R& g5 U, s; @  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
4 o' X0 S! {9 h/ Y  p->number=1;p->flag=1;; W0 y: l" d" d, H; T5 G, a9 M
  p->next=head;
2 I; ], [9 p$ A9 [6 ~0 |, C2 _4 l  head=p;0 o$ [$ ^+ f, C+ x+ _; D
  for(i=2;i<=M;i++)
& T9 C$ l0 I- Y    { s=(MONKEY *)malloc(sizeof(MONKEY));- O1 X6 b3 v' Q+ |7 o7 t# w8 Z
     s->number=i;s->flag=1;
: c8 \; W! N' T5 d: w! r1 h* x, E     s->next=head;
' V7 w. Y! ~( Z' l     p->next=s;p=p->next;
$ M" J# n! z( U; E7 M( k    }
" S, X; d, N6 w% N8 ^2 ]    p=head;
" s$ i& }3 I; i% t   for(;;)0 J- R' T% |8 ?! v0 h. c- p
    {if(p->flag==1)/ e$ i" C4 ^/ o) @% y( a+ \
       count++;
4 e, T0 `/ c9 Q0 X+ K* ]& r2 t& w     if(count==N)
' W& R+ s4 S- ?        {p->flag=0;
; r/ @* x) D: K         count=0;
, d* s  s1 L  G! j/ v" |         sum++;}
2 @# y; Q2 V/ }' Y! f     if(sum==M-1)3 V' b* R% K  _7 z% ~! q- D1 ~
        break;
" t# P9 e9 u) v% r. ~0 R     p=p->next;
' S" E2 h# m' f$ {+ F    }# m) q9 j# a4 k& I  E
    p=
( j. m3 T. x5 c% B& v    head;
" K9 ?3 D9 `( E" N$ y' V    for(i=1;i<=M;i++)
  F! U1 c; f0 g. ^- m6 a% L    { if(p->flag==1)* p' e# K; z! U6 g7 i+ H4 h; O9 g
        printf("\t%d",p->number);
  l; b9 H& u: z6 a5 {& `" \      p=p->next;0 h& F, ~: s  Z' p3 y
    }) h5 T( y# q  a1 _
$ F; i7 ]$ [7 P! O

! J* _& c7 y% V0 X
- g9 c# v. P/ d  [2 \- k) ?}

+ i8 u! a# q, V' s5 P- A: ^第二种方法:数组) y  N* l& W. H
#include<stdio.h>+ H$ S+ i! x. B
#define M 88 e9 D* J% T4 z. w0 e
struct monkey1 L2 ]  a) }6 k9 }- n
{int number;
5 A5 A9 a# B% Sint nextp;
3 a& @  I& I& y) j  r, R4 R: F}link[M+1];
+ M, R# j2 i, ^2 h# m
! t: x9 g; U; o1 i9 Rvoid main(): B- O2 e$ z6 D' Q. |# Y
{int i,count,h;5 P5 l* i5 v% e* [+ K& e, }+ j
for(i=1;i<=M;i++)
/ n- l" ~. j- N& ]9 u& N8 w{  if(i==M)
3 @$ T0 g5 ?5 j% l4 y+ @   link[i].nextp=1;
1 {4 \$ k4 I2 B9 Y6 R) v: Q6 z0 Q   else
! r. d3 Q  u( z$ J% T$ [   link[i].nextp=i+1;/ I" b6 D( Z) o
  link[i].number=i;( N. ^  O7 O2 Q: G9 s8 B
}
6 U/ l) o) I( iprintf("\n");+ a% s# ^% u- A1 U9 ~: @0 h
count=0;
5 e* S8 f; _3 m0 T: @: v6 Ph=M;& f" T9 {5 Y( ~8 U
printf("依次退出的猴子: \n");) h& c$ f2 ^# ~. f  l( k$ O
while(count<M-1)5 E8 F0 U0 |) j8 \8 q+ P
{i=0;
4 v- N- T/ I7 H0 L3 v: l+ Zwhile(i!=3)' _+ T7 F8 \% a6 ?
{ h=link[h].nextp;' U" h( L8 M( @/ {5 J) H+ y
   if(link[h].number)
: P+ U/ r( A/ d7 T+ J- [% n) M     i++;}
/ ~) |4 z3 P5 o) U& o* q" U) p$ |" c" I* W: d+ B
printf("%4d",link[h].number);" d  t$ m! Q* l% H, ]
link[h].number=0;
! {+ Z! g8 H5 F5 f2 ocount++;$ ^; g, `; B' h; t9 |
}
0 z: [: O& i- }" s" v/ {; ^! _4 ~2 o& S# Z! ~
printf("\n大王是:");
% I9 s; |& ?/ e& `  for(i=1;i<=M;i++)% v1 f: l1 @( |/ e6 @
  if(link[i].number)
9 B4 ^7 s/ b' G" z& g' D& H9 o    printf("%3d\n",link[i].number);
0 o! I: n! R7 ]5 E' U9 U  q- w, u2 j9 l$ S7 Q
! O3 `1 y) E, f+ x! h9 i
}

) B0 V: a! T$ u" C( C第三种是普通方法for循环
" s6 `1 p: i: f9 G* C, [, N$ y2 o
#include<stdio.h>" `4 o" Y$ Y, e
void main()
! `' ^+ u9 W9 P% [; u' M{ int i,k,m,n,num[50],q,*p;
( c3 a8 L+ N6 a/ s! x; p    clrscr();* ~; a: @) f8 X1 R# H6 ^3 ~
   printf("input number of person: n=");
/ r0 G3 o% C7 ]3 J    scanf("%d",&n);
1 i' O% `+ g. F& ~printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只& y( w% d1 x2 [
    scanf("%d",&q);4 n* o: k, \8 f7 c
   p=num;  R3 H2 u0 i$ i# d0 I1 j( S
  for(i=0;i<n;i++)
' z& l* b' ^" G$ D2 t' D3 @    *(p+i)=i+1;4 F7 }5 a1 q, G" e  S, @2 G1 x
   i=0;
8 h  [  P) d, a0 X   k=0;
1 i- Y* l( |3 R   m=0;" {0 {! r% @% D; ?; Y( v
  while(m<n-1)+ i3 P1 |' Z* |' w: t2 X, q
   {if(*(p+i)!=0) k++;5 T0 a. c' U$ G; s
     if(k==q)
, W% }! B( k9 `/ k! J/ M      { *(p+i)=0;# b& B% i6 ^, F- E) [
        k=0;( l: `. N1 s& n% X
        m++;
" p+ x( n, N6 ^+ N      }
' j1 R7 K! S2 [3 m    i++;: f/ u- ^7 f5 b4 d
    if(i==n)i=0;
. w4 M# y" _, G' q   }5 f4 j- B0 Z5 s* H. L- Z& j" J  l
  while(*p==0)p++;; Z. D# Z% x+ i. l0 u, d7 ^
    printf("The last one is NO:%d\n",*p);5 t' v* @; u5 \
     getch();/ _6 M7 G& [7 R! w6 Y& b7 @

" u! X  C$ J5 ^- ]6 M7 y}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
$ o5 ~" w3 `' S0 N3 knamespace 又费马达又费电1 B7 V1 T1 u" k! p& _& o
{
+ x# T" g8 U4 Y7 J$ y    class Program
, {: U9 Y; O' n, n. f& i    {
$ r1 u! g: f( j8 g        static void Main(string[] args)# L6 x3 D! r: _
        {5 H! r. _/ R" `
            int m, n;/ u4 T3 @. z* R* Z
            Console.WriteLine("请输入数组长度");
! b; Z8 t8 b# V  b/ M* p            m = int.Parse(Console.ReadLine());//m为数组的大小
0 h' Z1 B: l" J            Console.WriteLine("请输入要截取数字的大小");
, _# R1 \: D& J; i) g3 F4 }8 i+ E            n = int.Parse(Console.ReadLine());& N* b" E! [: K$ x1 ]
            int [] numw=new int
% n6 I7 q& a0 y$ H# F' o. u
, v' U! u) f2 }3 a, {4 p6 Q4 W&shy;&shy;&shy;;! T7 @. h- e: L: \$ J$ V
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
7 O0 D' [6 n; i( @            {* [9 z6 h) [9 V
                numw[j - 1] = j;
; W+ q. `' X; `7 ^- S- l1 u            }
7 v. \, K2 L! c  x            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
, `9 g/ H. ]+ T            while (d != m - 1)# S3 S$ i; T, D. Z# f
            {
& {0 O# N& S3 @1 ]$ b3 q3 l                if (i == m && d != m - 1)  F' K+ N# k0 T( M# `0 A9 i3 d
                {
6 S' {- y* c6 ]6 |4 b                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
1 m, L. M( e* X, ]' G" {) Q; G                    continue;% U/ T/ x+ @. S: N& \0 T" I
                }: p$ `7 ?  v. ^, }
                else% |* L9 ^8 d% v& ~2 U* ~
                {
, S2 q/ b4 |# s: F, A                    if (numw[i] != 0)
$ x! a! O; B' q) ^, H- ?! x8 g                    {
8 ]& ^; x6 j& x# S( j. f  o                        i++;& N& e' f  ~+ ?2 @& d5 u  ]$ \
                        k++;1 [; @; @; U/ r& s' M1 `
                        if (k == n)" U! H' o6 l, i4 n
                        {* S( J( M! O& h! e) m+ i$ o* H
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" Q7 ?9 Y% y5 B9 ?. c
                            k = 0;" H0 T. O: e7 N  {% v
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小14 v& V& N3 [; A! E/ k4 N# u
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 r, a9 W5 ^$ b+ g                        }9 D8 [6 y! T9 i" ~3 Z1 r' c
                        else//输出暂时还没有改变数组元素的值
4 ~1 K, M. D5 R; Z, Z3 T                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);' P5 B: _6 B) A! M. ~, C
                    }! {7 H3 z3 g9 W, w, U
                    else4 t8 A7 Q& B1 }7 ~- v, [+ E
                        i++;//数组元素为0,直接跳过,不计数。。。$ Q: M4 q4 ?3 B
                }" U/ K  J: e: O! w5 M* y( c; _1 C

% w. N9 |/ A4 ?5 n
& |  m7 P5 q# W# f            }//结束while循环) s# W7 z2 F- U+ K3 r4 c
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦: L9 O9 Y3 ~* k9 \
           
( |. v1 t/ i% X, g% t1 R                if (numw[i] != 0)9 o- {  W9 W5 q* p7 [
                    Console.WriteLine(numw[i]);
. t, C+ r& T: r2 P- [           6 }& ^6 W& ^! I6 k$ A' [- E5 V1 @
            Console.ReadLine();4 m* T* D: v' m( R; l
        }6 U& u% w1 D- R3 s+ |* J0 U- A& B! U
    }
& I8 `, u  v7 q6 Z% J, N}
4 X3 }5 v; H% x' k/ c1 z1 ?% W$ q
小甲鱼最新课程 -> 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-1 17:53

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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