鱼C论坛

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

猴子问题

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

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

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

x
大家好!
3 D, R4 o. ]7 X' b% ]4 u这几天我在忙着编一个问题,我用了一种方法编出来!; }1 k  j. `% p/ [/ D8 G0 G
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ t4 S# A* }; r3 y
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 1 |6 U) u8 d6 E# E5 O2 A# a
, p$ I. g  c8 q$ j; x, ~/ s
$ a7 k6 m8 m4 c* K3 u
                            题目/ p) U% \/ }9 \5 ~3 A6 U+ Q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。8 n! H; g& I# K4 M3 O: E2 e1 t4 ?
第一种方法:利用循环链表! ?0 z: [: I) E7 S& Y: x
#include<stdio.h>
* }8 k, Q5 ?) _# G; m6 L#include<malloc.h>! v8 O) u7 X- t
#define M 8            //共有8只猴子% L# ^4 P( E; [% }" p
#define N 3            //数到3只时退出第三只6 D* F! ?/ C7 r; J, h9 `( M  P
typedef struct monkey7 H6 k$ c" K9 |( m6 X$ [) C. K
{int number;1 I# ^2 e2 Y& _1 \. b3 V2 T
int flag;
# ~( P4 l/ g- U& P% hstruct monkey* next;! e: j9 V+ B0 i1 f2 L! F" l1 U
}MONKEY;
; V+ ?/ u3 k6 {# Bmain()
5 Y' ~9 ?: n: B6 h( l# v{ MONKEY *head=NULL,*p,*s;- J: p7 a2 [/ g5 `6 X
  int i,sum=0,count=0;* H  E# t* E( K' y
  clrscr();              //清屏
! E' M; {  p# g+ w# A9 Q  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' I8 T' w  D2 Y2 a. ?' S$ @
  p->number=1;p->flag=1;
1 o# t3 v7 D8 P5 f7 X, d# s% i, a  p->next=head;: x# V& e5 a) h6 m0 P9 d4 w) O1 [9 V
  head=p;( l9 _9 I6 y( |- ]1 G7 P+ a: Q! J
  for(i=2;i<=M;i++)
( n6 n4 @; d# ]+ |& M    { s=(MONKEY *)malloc(sizeof(MONKEY));
9 ^. l2 a  l5 D8 ~     s->number=i;s->flag=1;( w5 q) q4 s3 ^
     s->next=head;, d) U1 O, T+ ]
     p->next=s;p=p->next;5 s+ R/ M- |6 q: E/ @3 ]
    }
$ p/ a) M2 T. j1 b  r% [6 m; S: m4 c    p=head;% Q) A  d3 s, j! ]/ @8 F2 x1 K
   for(;;)
  T. O9 r5 v* ~0 A/ ~% D+ }4 p    {if(p->flag==1)
1 {- d" L% [( P: y0 L1 z       count++;
8 J  `7 h& u# S1 s     if(count==N)
: W9 c3 ]# x' h( C9 x+ O1 U        {p->flag=0;" ?3 m' u8 Q" w$ k
         count=0;
/ N# X- [7 A$ X3 b1 y9 n. \         sum++;}
. N& |( I. e, T2 W     if(sum==M-1)* _+ j1 c* A; p& }0 Q; K9 O+ x
        break;1 z8 F4 c& s5 H/ H: s3 q2 ?4 a. i3 }
     p=p->next;8 `+ y' S8 M8 z
    }
; m$ }0 w! n, W: Q! T2 u    p=. p4 E# h7 C0 W# h$ i0 o1 J
    head;
" l' _1 n5 Y4 `5 f2 E, Y    for(i=1;i<=M;i++)
' ^3 b& y) i; C4 D6 t    { if(p->flag==1)
1 }4 o6 G1 ^3 l& l( v, c& H8 ?        printf("\t%d",p->number);
1 c  l2 \! T  F2 M, Y! ]  R      p=p->next;% O0 {7 @' T: w- U2 j1 T
    }6 P( s  M' x  W6 E- W

# G4 k. P" S2 u; O: `0 w0 I
; U( h) z0 z: l# U
9 X* x/ |3 x  b* E4 E}
: ]  l4 s% f1 l$ r
第二种方法:数组
* j) D0 ]* p! U! q) C3 T" t#include<stdio.h>, L- ?  _% m) F8 f
#define M 8
& h  T; R9 c% s2 f! Ostruct monkey* `! |2 g" s2 t! K9 o
{int number;
3 ]) o5 W9 I( L! u: kint nextp;
. E/ z3 S" j8 O0 ~6 {) d}link[M+1];$ r. G" p( v! ~& P) Z; ?. ~
* O4 M/ h' V1 ?2 W8 s1 M
void main()
) t0 n: f2 p# {. B: O  q# Q% b{int i,count,h;
4 n7 D% Y4 m0 O( `for(i=1;i<=M;i++)
2 `+ O/ }5 z* _2 r! K{  if(i==M)
5 P9 @+ ^5 K8 }& s% ]   link[i].nextp=1;4 o4 ^4 f- @. e( }: h8 s1 r
   else
- g! b. y/ E- u# o   link[i].nextp=i+1;( |/ f. I/ a: H# V  q" y' w
  link[i].number=i;) |5 d4 {  e" W# j- c, D& c
}- l. x# l. T% M' g) t7 ]! P) f
printf("\n");
# i4 W1 g9 L; ^count=0;
; O6 s2 {  C# z: i1 {h=M;
' }, s( I- t+ Eprintf("依次退出的猴子: \n");
: n# w: k# ]* H. G* f! f; C$ G  R. Qwhile(count<M-1)! S) P' H- P2 }! m1 U# g& O. G
{i=0;- N" K+ l, f, q3 K
while(i!=3)* i. D3 M  F' d" a6 O
{ h=link[h].nextp;: A4 g/ l7 h& P7 O& e
   if(link[h].number)
* ]& \- \8 J; X; q, E     i++;}) u6 P! o* ?0 u  u" Q) Q
5 I" H* v% S/ q
printf("%4d",link[h].number);
4 g% V5 L4 B3 X# K' k( m4 Blink[h].number=0;
! u+ {) @0 V# t9 d% fcount++;
( T& k- [# _  y  @! x3 g2 [+ c}
/ y( G$ J. E0 {: S* J: Z/ U: Q, W+ \+ O- r' q# b# v) _) Z: |
printf("\n大王是:");
/ \: p: n! ^" K) Q; U2 y  for(i=1;i<=M;i++)4 C9 `" \2 x1 H- k: u
  if(link[i].number)+ j# ?' h5 ^; @2 q
    printf("%3d\n",link[i].number);3 H' }1 S# S, p# h0 {
/ _2 e+ ~; R5 r, l6 v' }) w
# b0 ^" H$ i: F: O
}

# ^5 U0 C# a& v! w5 Q. H第三种是普通方法for循环

$ J. p# i1 |6 |1 H7 _7 G* ~/ i#include<stdio.h>
" g' m$ t" I: E& ^" S; lvoid main(). s. m$ d! r& w$ h5 q3 v9 S6 q
{ int i,k,m,n,num[50],q,*p;6 V, G) {: L  e# G3 p
    clrscr();* m, P' e) t, z1 ~9 ^
   printf("input number of person: n=");0 f' u0 D: u' S- ?
    scanf("%d",&n);
0 K5 s  e7 m+ i6 k- X; O' Rprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
2 q5 f/ K$ x: M1 X1 K    scanf("%d",&q);
4 c* N' ~7 _, v8 z. s   p=num;
# h- P6 W! o( j' ^  for(i=0;i<n;i++)
9 q! x( v/ K' y: a! q2 b8 D  h    *(p+i)=i+1;1 Q) D- D" a* o8 [' w+ p, U
   i=0;* ~6 h8 O' {: B& f7 o) T" `" N# @9 ?
   k=0;
& F3 V9 u- `  x7 _; M% @+ n   m=0;
; g) M; j# Z* D" {2 Z6 q& C( c0 T  while(m<n-1)
( I- Y( R. m% D9 V2 c' z   {if(*(p+i)!=0) k++;
0 q8 \5 L. b5 \0 h- A0 A     if(k==q)  d: a1 ]$ ^1 f$ Q- l
      { *(p+i)=0;
! C+ O) P' w+ s( Q9 n" `6 g4 m& d        k=0;
5 ^+ Q8 {$ B* @3 f) N) Q        m++;
$ V/ n" ~9 v+ b      }
* @# r9 W- X! F  a    i++;
# \5 f+ {% u! |7 t- b    if(i==n)i=0;) K& s5 v7 B" D2 z" [! n0 x; U( B
   }
2 ^  A: q  d, G: S. ~  while(*p==0)p++;
$ n  L" I& k! x3 `$ f    printf("The last one is NO:%d\n",*p);
9 X" e9 Z" T3 j( Q! _     getch();
: q6 G6 _# v) `1 h+ R+ i, i( P6 e: _1 e$ ~+ V( A
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;/ m$ K# V% c+ D* U
namespace 又费马达又费电
) V# y" x8 C  e5 P/ W2 [0 G8 K{+ G: N8 ]3 `" p5 l/ [
    class Program
9 @1 {' \- S# O! y+ B    {) ?' N; _( E3 }. b% s, v
        static void Main(string[] args)$ |/ E  a  x( ]  B; e5 ^+ L  d, I
        {
. q8 f' ?9 n8 x5 U" B            int m, n;7 K0 Z% v1 @2 k: D) V/ `' y+ r; n; t/ u
            Console.WriteLine("请输入数组长度");/ Q7 n+ B* ]/ w7 l, _
            m = int.Parse(Console.ReadLine());//m为数组的大小3 |- X% }& b, d) V, [5 j' T
            Console.WriteLine("请输入要截取数字的大小");
/ Q# s; @# ^1 G) ^' i            n = int.Parse(Console.ReadLine());
4 D+ J# R3 g3 z: Y            int [] numw=new int
+ z& \0 o# S2 n$ r! S: u0 P6 B" e7 @" [: ^" F
&shy;&shy;&shy;;# s6 G2 d6 s; ^* w, k% p
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数8 W5 e) L0 Z3 l1 T  h/ D. k3 k
            {
' P5 f8 O/ P  i8 s& J9 r4 w6 @! E                numw[j - 1] = j;
2 ^' s, a/ u& ^5 B2 d            }
7 r& c' |- ?3 c+ W2 C* o            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!- ^% w6 S5 S  n1 y& K; L1 F
            while (d != m - 1)2 x# N% I" D; [# Y! s
            {
! ]: U+ T5 e1 h8 u                if (i == m && d != m - 1)" {' Y* R5 D4 J3 v$ y2 T
                {7 m* [3 V+ I. x3 r8 m+ D
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!) j8 a$ e7 w) G8 K9 y+ V+ v& B* [
                    continue;
% L! ^+ I% E/ H% g7 @( l, K( C                }; }. x6 v# g  `0 M7 G3 K# c
                else! M- \$ T' {0 i' {% {) g" T( B) V
                {
5 ~, r2 J# w/ w+ c                    if (numw[i] != 0)' M( b* q: C. Q* w7 A7 t
                    {6 N1 C$ N( ~1 H9 G2 q5 O# Y; W
                        i++;' z, x$ G# ?7 L6 i1 i3 E
                        k++;' E9 x+ Q4 E1 j9 S
                        if (k == n)
% `" G: ~: ]1 M4 M6 M                        {
; _! o" b& E; `  M                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
% P0 u% p3 T" m1 f# Y% d! O6 v7 B                            k = 0;
* \5 Q5 N4 F; e1 b              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
% a% c: U8 V% b! r) |" t                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
0 {3 x2 @8 l. w* ]* \                        }  ]( Z, _( X# ]4 q+ A7 W* M2 R
                        else//输出暂时还没有改变数组元素的值
/ d* U( _/ O# h. d) D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ }/ G) {5 O3 F3 y5 k: G                    }
0 _0 O- D* p" w* }                    else# l' J2 e" o# l# d+ E1 ~2 y8 Y
                        i++;//数组元素为0,直接跳过,不计数。。。. t: A* v5 n" O- b6 h* k) I
                }0 b2 S5 `) d% d$ m
8 A/ @. v  @6 W8 E

* D' p- o3 i! }. M4 R            }//结束while循环
5 a* W9 Z' _5 v; _1 }0 ]            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
  _. H% k. G% v) L+ ^' J           / e+ h* q% Z" o5 L
                if (numw[i] != 0)
; G) z7 D+ T& G9 `                    Console.WriteLine(numw[i]);
/ P# s; r* H, |7 I           
! S# k$ n4 [. ?* a7 z            Console.ReadLine();
6 U9 n- y2 `6 R. B2 Q        }3 m# H& `% C7 |! X7 S; \% r8 k
    }6 ]$ m0 o/ Z4 M) {
}
3 A$ d1 ]4 s* j9 B& ]
小甲鱼最新课程 -> 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-20 11:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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