鱼C论坛

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

猴子问题

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

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

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

x
大家好!: n9 Z! J% Z  T' m& r% N
这几天我在忙着编一个问题,我用了一种方法编出来!7 l; u1 b# {% V8 s& F
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
1 K) G: Z7 H( L+ D; N4 R  G注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激   g8 K% Z4 w, x: ]; k

) R! U0 \4 t0 z3 t3 m* A) \: B" v6 [- h9 v& j* U
                            题目1 d  |+ w  O& Y3 v) r- [0 h- N- i
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。% [$ @8 X% T! ?4 i6 T& Z* W
第一种方法:利用循环链表
) f1 }" J) B2 I+ f% Y4 b8 t7 k9 l#include<stdio.h>
2 w, J$ ~; r) y" I$ c$ s8 j#include<malloc.h>
8 P: l1 E* ]$ F5 }7 R" U9 H#define M 8            //共有8只猴子% o* _* S1 p( h: J
#define N 3            //数到3只时退出第三只
0 P! H1 T! [# otypedef struct monkey
2 Z9 h' z: w$ Y  s{int number;
8 v8 x6 S/ G' C$ e, R! E* Zint flag;
& |  _, m- F7 ]% w9 {/ h; qstruct monkey* next;: v$ q$ A2 u  _+ n/ ~
}MONKEY;
0 |6 L5 k- M' }) `$ U, U) emain()) v% p* P7 w  O& B0 j' Q( l
{ MONKEY *head=NULL,*p,*s;. |1 l3 T) J& [
  int i,sum=0,count=0;% I1 t* U: m$ b- j+ O; k- x
  clrscr();              //清屏0 c  ~  J0 k4 L5 }0 O
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
" J. b2 `) |1 R) u4 q  p->number=1;p->flag=1;4 w5 p3 i# e! z* T0 v
  p->next=head;
! |. H0 r+ ]$ M2 Q! n% L5 ?  head=p;3 P/ ~/ u/ J- s# }& r9 G
  for(i=2;i<=M;i++)
6 X7 b9 x0 c$ s7 O  @) T    { s=(MONKEY *)malloc(sizeof(MONKEY));
6 ^' o# _# T5 _4 A' F; k, {) C! i     s->number=i;s->flag=1;
, A# Y) X1 c/ I6 B6 B     s->next=head;) d& r5 U  m. A* h; M8 U6 p
     p->next=s;p=p->next;
2 r+ s/ Y8 W2 @    }
3 A6 Q6 H; _4 ]8 D1 p8 x: K    p=head;! w0 o) H" {) P5 j
   for(;;)$ D, N1 o$ R# l; l. {# `
    {if(p->flag==1)
, N3 n( h9 g8 F/ Z( O       count++;$ g" q& W5 H- |
     if(count==N)
" j7 S" D4 v* z8 Y! E+ F9 U        {p->flag=0;
5 j" F: `" P/ c: _8 L         count=0;6 G. q- Q8 Q* R9 {% _' E; Q$ k" |
         sum++;}) V  P, i, `/ o+ i. ~& s) C
     if(sum==M-1)
; l$ F5 K  b2 V        break;
0 ?# |' \* y7 L6 u. J9 f) l: P- G     p=p->next;
- g8 n, Q  h3 b. E1 W1 i* C    }4 K, q: M% X# A1 Z1 |% E
    p=
  y) p5 z: o4 T+ W6 _, q    head;- V9 o. c: x- K
    for(i=1;i<=M;i++)
0 o3 s" Q3 g& i7 d& Y& Y    { if(p->flag==1)
1 O! C9 A7 r) u( H- N        printf("\t%d",p->number);4 `2 r& b, g, U) `4 t5 _
      p=p->next;
+ F: O( e1 r5 T# Z: D    }+ l7 H. j  [0 Q  Q8 M

5 q  A0 c2 E( F$ z, X5 g( @1 N( U; ?% S* |$ ~' \( L# X3 W7 i
+ G( N5 V: W2 d; S3 h% A& `
}

: R- M! a# L: ]第二种方法:数组$ d5 z, c2 I7 `5 U6 H' u; j4 ~
#include<stdio.h>/ A3 I8 P3 w& k; K
#define M 80 Q! l! C* C; A
struct monkey
9 E8 i4 P+ R7 f* m9 V$ w{int number;
# v9 d9 I8 D/ d( q8 y3 lint nextp;0 c2 P1 A' f9 E
}link[M+1];
! e6 [. D1 D3 G; {8 F  f9 ]: c9 b: t2 O: }
void main()
" j( ^3 x4 m* e$ z{int i,count,h;7 \* ^$ [) R9 n+ ~" s. t$ n
for(i=1;i<=M;i++)
& _  B& S+ T2 ~2 s' m7 Q; t& U{  if(i==M), S* R4 y; L  D% {+ v( K- \- E
   link[i].nextp=1;
0 D3 |8 _: h3 g. k0 `1 a   else/ F5 q; c  g) N7 P1 Y- i
   link[i].nextp=i+1;7 e* S7 v( v5 Y) G0 w
  link[i].number=i;/ K5 z" K8 E. e- \# y! u6 X  Y
}
4 @, [2 J0 g1 z- D! f0 c& Nprintf("\n");/ ]6 t9 v2 E6 s, F) r4 |# E4 p& O4 j
count=0;
8 y2 l5 T# W* s! u. Oh=M;! O* b' ]  ^$ _5 |$ h  u
printf("依次退出的猴子: \n");
& f6 F5 W$ B% G& ?5 _- Iwhile(count<M-1)$ m3 P$ |4 S( Q
{i=0;9 T  U4 k& L. U' L' J, n$ z
while(i!=3)$ Q# E# @* ?4 w$ H; E, Z9 U
{ h=link[h].nextp;
7 }; z" d' S, x" r9 |2 V+ F   if(link[h].number)
, H1 E/ }( H9 I. y* q# R! K     i++;}
! u5 R6 p2 n& m+ w( y9 ^" U  S. l& O$ N1 k
printf("%4d",link[h].number);
2 _# y1 P4 ^) C# L1 ^  Z- qlink[h].number=0;
2 T7 e9 _6 U2 Z- z" \; icount++;6 g  `4 N4 q. }9 [% h
}4 \" ^; N6 x) j* o; s! O! t. @3 ^
, ^- `2 U3 y% o& _9 Y# F' g
printf("\n大王是:");% [. g7 a* W" d! b1 R4 l3 `, p) [$ W! [
  for(i=1;i<=M;i++)
" [# ^# A; D5 _' d) {  if(link[i].number)/ [5 l8 z0 V3 V5 ?& S
    printf("%3d\n",link[i].number);
) p  Y% v6 \. q5 v$ ~9 M- _# j
, |" h% s  i; Z, V5 f4 v  H  P: h5 I
7 J6 N2 `, e! e9 L( V}
3 p' P5 {  ]/ e# ?
第三种是普通方法for循环
' M9 d7 K; T/ y8 D7 l5 M
#include<stdio.h>
' E' ]# V8 A8 c  P. _; v7 h: |void main()
# p* E5 ?- h6 O) c. c4 K3 G{ int i,k,m,n,num[50],q,*p;3 I# l6 ]. A& j) N, ?* d4 t
    clrscr();
# q. t+ f7 Q9 o; [' `& r1 n& ^   printf("input number of person: n=");
4 `7 G  P% N+ F4 Q8 R  m8 T    scanf("%d",&n);2 {& P! K( _/ ~6 h
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只; }' m  ~, Q: g6 z, [* O
    scanf("%d",&q);
; K. R1 q5 t6 @   p=num;8 \7 x% g6 t" x) ^
  for(i=0;i<n;i++); B4 `- u9 z+ o$ v3 X
    *(p+i)=i+1;
+ W4 Z$ V; s# O5 y   i=0;
6 V/ G# q+ U! ]/ z3 b   k=0;
, M% y, h: @4 L/ t) f/ m   m=0;
& P. w7 ^4 v8 ]+ a+ h3 N  while(m<n-1)
# V9 P6 n# x) L1 a$ Z5 d. d   {if(*(p+i)!=0) k++;
% b0 L1 V. q. M5 \     if(k==q)
% |0 h& g' H7 J2 A8 @& i      { *(p+i)=0;
1 Y3 ~* ~" a4 s/ P9 b4 M7 F        k=0;
* R3 A/ B) Y% N: b7 C" f- T1 @        m++;4 ~) q; p4 W: a! u! _
      }
4 H! e6 Q3 \; |9 x    i++;
/ A3 ]. d' H% F* d7 k9 j7 Y    if(i==n)i=0;' U# v6 K* F/ ~  Z
   }8 u( I* P6 b# m6 M
  while(*p==0)p++;% y, N7 _5 A; ?0 z7 x
    printf("The last one is NO:%d\n",*p);' |, \& }4 T" o+ Q/ i+ k
     getch();
: D+ C" Z& N% B; d0 M$ Z: L" r5 y' s1 h! e
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;1 C8 F: @$ Q- Y( ^) U  c* T3 ~
namespace 又费马达又费电3 k- v* t9 `0 i
{
: f& V- H1 W# `+ E3 d    class Program
* J$ D; ~) ?" Z/ p: l    {5 T; i% G) f9 k
        static void Main(string[] args)
; n- j% F/ b! `7 ^* h        {
. _2 P# x  }; q! n            int m, n;
' g2 b( V, H0 [  p( \            Console.WriteLine("请输入数组长度");/ F) i. s: F8 f( o$ x
            m = int.Parse(Console.ReadLine());//m为数组的大小$ k/ D# t  A3 {- I& [" a# o" N
            Console.WriteLine("请输入要截取数字的大小");
: [% }' U/ ?$ a" f* s+ i  b            n = int.Parse(Console.ReadLine());; I6 L- o7 l0 j; S
            int [] numw=new int
% R, T, d1 [& Q
6 Q4 e7 J& ^6 |! p* U, D" ]0 }&shy;&shy;&shy;;
+ g) E4 a& F) r9 x! N, ?1 L# k            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数) S0 d- z, T1 I+ I
            {
0 c8 `) C7 l( p+ L8 ~                numw[j - 1] = j;3 _: ~9 V& i% i. d9 S
            }
) v. }" r9 F1 y" y; K' o/ K            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
% d* A: _7 Q8 t8 h* h            while (d != m - 1)
2 R% z2 Z" p" ^: Z6 x3 {- S2 |            {( i* V" h  q2 [
                if (i == m && d != m - 1)
0 v* l" t& k4 ]- H5 G' x! t2 U& l                {
5 X. u! W1 Z2 s* @% J& F% C! Y' z                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
; {1 q7 H& v1 ?0 ^3 z) @# i2 n                    continue;8 y! [+ @8 g3 a5 `
                }
" i3 p. G2 j6 t* N; Z                else
* `; x  f7 g1 N$ W/ r+ o! V4 v                {
6 s( v/ ^3 j" d0 z0 Z$ i$ I( x                    if (numw[i] != 0)7 ]$ W' y4 g7 ?
                    {5 l  p! p4 _* u: l' M) W
                        i++;/ L5 H9 z/ O- A+ y
                        k++;
. K. b1 _3 r) g, T  |) J8 F                        if (k == n)- E+ [# t' w$ f" E/ N
                        {. B9 }5 z) P7 x9 i
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
' ~% ]' J+ y' b8 |) _+ A: u2 X                            k = 0;* A! H7 k# J3 u8 p: S
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小11 L( A3 e+ X4 e. n
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
; \; i6 e' m! @7 ^( R                        }! p6 w! T) V) l
                        else//输出暂时还没有改变数组元素的值! t- W, T" ?# b- u& u1 H7 R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
' i9 }, F- B! k5 N. |                    }
( ^/ Q1 B: H, Z9 W                    else$ U6 `. C. `3 a& e  C! x9 v) j
                        i++;//数组元素为0,直接跳过,不计数。。。
& T) o0 t" O5 h4 q8 l1 M: ?                }
& `. t7 f- B# o6 T1 j" l ( [% l* D" f; E& O4 x2 W
1 s3 d5 W$ p$ w. R2 F
            }//结束while循环
0 S- B, w" C2 |            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
* @6 U* u6 [' E: f3 ^. W% x           7 |3 z# Z' l/ j& y0 {  b2 q
                if (numw[i] != 0)
  W# S# f% [  Z, y" @% l$ J, @                    Console.WriteLine(numw[i]);
6 n1 q% P; ~; G# J7 S/ k& g2 E" g           ! x; F/ D/ s3 x' V2 s; F9 q
            Console.ReadLine();2 R" N8 k9 e0 s4 Z8 l: F/ D8 m
        }* r% Z+ `- D# Y8 r2 _% o3 n
    }6 y* N4 ~+ t* [) D6 s
}
" A5 G, o, C7 [7 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-28 12:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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