鱼C论坛

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

猴子问题

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

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

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

x
大家好!
6 n+ p  j& e+ k这几天我在忙着编一个问题,我用了一种方法编出来!: N( ^( x( r- X
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
4 {$ f4 }9 g3 }8 S注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
0 k1 H# E7 l8 @* _% }  g9 F, B- i, K* c

) }9 I2 w4 Q" e% l
                            题目
/ r2 E! [8 [. b* c. ]山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。" N8 [2 n9 R3 y/ r
第一种方法:利用循环链表4 `+ e& o" `% p! j
#include<stdio.h>8 k" Y, y; o, s
#include<malloc.h>( @1 t( }0 z# c0 w# g
#define M 8            //共有8只猴子
! C: K  A& ~* d* t$ @, Z#define N 3            //数到3只时退出第三只
9 h5 {( r7 W) \  i# Wtypedef struct monkey: L& ~( s; c' `& ^
{int number;: ?3 A4 ]! u9 N1 K6 `2 L7 X3 h
int flag;
( o" V" k6 x* r  e6 e! Bstruct monkey* next;, c+ F5 R" a" _4 a
}MONKEY;6 q1 s. |! q- @8 U( Y: \2 |5 I
main()
2 F4 R. |* n. C+ {# v5 }( _{ MONKEY *head=NULL,*p,*s;
5 o) f7 N) j4 [; P% |' v' p7 Y  int i,sum=0,count=0;6 L' t" L0 o+ D: n' j( G: V
  clrscr();              //清屏
* q3 K; J& M& ^4 D2 e  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存* s% D( L3 k, s
  p->number=1;p->flag=1;
# Q# D! K0 K$ h" H; j$ r# P2 U# P/ E: I  p->next=head;
5 L) `6 `3 J% d0 c1 R( L& m$ c  head=p;
; n6 |2 X8 ?! h7 O, f  for(i=2;i<=M;i++)1 i( h6 F- N8 Y9 T8 X
    { s=(MONKEY *)malloc(sizeof(MONKEY));# ~' I/ M9 h$ B- `# ?2 r# h
     s->number=i;s->flag=1;2 T. O* O* ?1 H$ l2 m* _
     s->next=head;1 p8 n5 K) [" D; d
     p->next=s;p=p->next;2 [- ]! `( a+ T4 k$ d) {- m# H
    }
& o8 f+ {, w5 V# C    p=head;7 \+ ?0 X3 Z% I+ f) f# {+ |
   for(;;)! i/ G7 b% P9 |, h2 X0 R
    {if(p->flag==1)
( M, D; r3 B+ H( y! M* q% r       count++;
0 w0 Z* A/ _! u7 U# A- j9 ?( }     if(count==N)$ t5 T4 i6 i6 p  }# n6 B2 e/ }
        {p->flag=0;
* B6 i6 {. w6 I: a" M0 k         count=0;1 ?) p' V  ~8 `4 f
         sum++;}/ `& [; s* n4 G8 c2 ^, n- m
     if(sum==M-1)
, C( }+ l8 F2 |% P. i* [* s7 x3 A        break;
& \: _; j4 U: R9 ^     p=p->next;
) O# Q$ q- k0 C! s5 {    }
( |6 {7 Q- z' j3 L8 V( F: `' s    p=
0 m- i! i6 O  x' a4 }! Y$ x    head;
. Z2 p) c& F6 {+ R+ h* K- |1 z    for(i=1;i<=M;i++)0 q/ a' g- l- L
    { if(p->flag==1)
" x: y* B4 O+ M: X8 p        printf("\t%d",p->number);0 }3 ]* B" N5 l+ Q5 W8 C! M
      p=p->next;
& w( K  c8 J0 x# F4 l  f    }
& D  a: Z. }4 l* s: e4 i
% \5 q  A2 \" {2 |$ ?. t
. s$ {5 \1 t; ^% {- K, f0 _8 Q. _; m+ d0 `1 J9 W0 H1 h
}
: n* n4 `8 h8 M- m+ p/ H
第二种方法:数组9 d9 y2 Z) q  x; L9 K  _6 p
#include<stdio.h>4 N$ y* A7 R# ]9 Z' f7 O1 \% X
#define M 82 M. f9 O0 Z9 |$ c
struct monkey" p) B% x" Z: U- ~
{int number;
/ u' k7 h! V/ @" {int nextp;
% C( N) c7 K: D. o7 h8 P}link[M+1];8 _9 o# U* M7 ?- x6 ]
0 A' f: m& y7 j$ R
void main()2 q0 I# ]8 ?, y# \) e& c
{int i,count,h;: [: B9 n* f4 T- [6 T6 W4 o
for(i=1;i<=M;i++). w* I. e4 ?+ i( q/ E$ D
{  if(i==M)
! z, x5 U6 \8 b; c  [+ N! V( B5 h3 b   link[i].nextp=1;
$ h1 W! y3 ]4 S; {; h5 c   else
) n4 I  i: d6 H' Z9 a   link[i].nextp=i+1;
2 g+ G! \2 U. V, y( f  link[i].number=i;9 n# ^$ [! y& V! u. u
}3 U: k" E7 S1 J7 {) P# Q
printf("\n");# V+ _; h$ U# P& R
count=0;* O% r. [* x4 B! b5 u) D1 f
h=M;
1 c, t/ U9 G7 X) k* w3 Wprintf("依次退出的猴子: \n");
9 ]! a, x, d9 Q( t+ Pwhile(count<M-1)( l. R  q; H: e
{i=0;
) k& w, `3 B" `" j1 a0 n7 i$ t8 |while(i!=3)
# Y" [% g! O# p5 V7 f0 E{ h=link[h].nextp;3 [3 f# c1 H  q7 \& e
   if(link[h].number)
0 D3 f# j/ S; T- S     i++;}
3 @, {. j/ S3 @- D/ |" T
( ~. A# R/ t. N5 u( [- Jprintf("%4d",link[h].number);. p% D' w( D, A% G2 x
link[h].number=0;
( e1 n3 N! R. Q7 ]7 Wcount++;
: K. v) T" e9 u. H}7 P3 p  O) [* |' P8 x) p& R5 V, v" m

5 A2 N6 \6 m3 j+ K7 @1 Sprintf("\n大王是:");
' u6 {0 s, x2 C! F. i1 N  for(i=1;i<=M;i++)
, b" v: R6 W4 h1 d! G  if(link[i].number)6 X- |6 ~2 n% L- Y' J2 H8 Q' P
    printf("%3d\n",link[i].number);
" h0 ~% B( U' h8 k% j) v+ n: P1 h- w
5 e4 o. W6 N+ d) U* o
}
* k; Z' `- ?8 w6 y
第三种是普通方法for循环
7 j3 i# f8 i& u! I
#include<stdio.h>2 g5 z% C* z. ?; w/ t- t% P
void main()* N1 F1 w( U+ P7 U: b. V$ X
{ int i,k,m,n,num[50],q,*p;
/ M0 o; a% K+ C/ z, l    clrscr();
$ k4 w3 L$ j6 H   printf("input number of person: n=");
0 M, W" y+ G) h2 T$ H3 e% {% m" {$ e    scanf("%d",&n);
, m# I& ^  l; U, O6 pprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
; L7 ]9 ?5 u# c' B    scanf("%d",&q);
% }" ~5 R# C0 f   p=num;
6 l5 q( h) x0 v/ n. ?1 c: e  for(i=0;i<n;i++)! p& o4 j) k5 x/ r9 ]9 P
    *(p+i)=i+1;" G( k5 J- W' \( y& p
   i=0;
; o/ `. J, u3 F" `* E" G   k=0;+ H; X1 k+ Z$ d3 X; F! [: X  X
   m=0;( W# j, L* @) l- U
  while(m<n-1)
! z( p4 Y# i( r5 ]% w* N% R% Q7 o   {if(*(p+i)!=0) k++;
/ p! I# q9 }0 c/ b     if(k==q)9 `8 ^: `" M2 A
      { *(p+i)=0;  f) M6 z$ D) _1 i& H
        k=0;( C5 G2 j" @2 r9 f; r+ j4 N
        m++;2 _  s. T2 ^0 U8 l, y) x& J
      }
  @! Y1 Q7 c3 R8 s: |1 ~    i++;2 t. |/ Y8 \' P6 B( Q6 B
    if(i==n)i=0;& x* a, f7 \$ N2 K5 U/ Z- R  z1 I; N
   }
7 p1 N# ^' H: q8 a  while(*p==0)p++;7 S% _9 D' s6 ?4 ?( i* p
    printf("The last one is NO:%d\n",*p);
: U3 S5 b8 h+ E$ H6 H     getch();% h/ ^+ v0 w# b: c1 B" ^0 O! T; t
; z% Z" M& \: r7 L# s
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
2 s7 p8 H; _( o. P1 Y. c. znamespace 又费马达又费电, p; i2 Y9 Y: }! w& o3 u7 Y/ V
{
6 v: {- F; S1 S) ^! S0 Q3 i" n/ |9 D  n2 q    class Program! @3 o3 W7 B  d7 z+ U
    {
/ r5 s) _" Q" Q        static void Main(string[] args)
0 A4 d. L- s, W9 ]# m0 o. c% _        {
$ o# A5 G* f# U            int m, n;# S* J* D& ]% _& w
            Console.WriteLine("请输入数组长度");: r1 Z0 C: T/ \$ C# i) I6 e/ p6 s0 U& U
            m = int.Parse(Console.ReadLine());//m为数组的大小0 o! ]+ s7 g5 z' Z, O! Z
            Console.WriteLine("请输入要截取数字的大小");
+ j% b$ i- K) |; q4 u  K! d+ q$ j            n = int.Parse(Console.ReadLine());
. g: l' ], V  n7 e/ Y            int [] numw=new int
8 v0 v, {' d7 Z- ?/ H+ S; b
8 G3 s1 `) Z' \8 H3 A&shy;&shy;&shy;;/ V& H+ p' I: ], z
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数8 [7 K  x7 X, T4 {& o* A
            {
1 I# g6 E9 \4 k( }' A; \5 \                numw[j - 1] = j;
6 s. Y6 L( z- l* T/ y            }
. f. [, b  r4 z- b            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
. i/ D: p; {4 S1 b4 ?            while (d != m - 1)
: V2 m/ z- K/ \0 [# x            {& O: n& W$ u3 B: f
                if (i == m && d != m - 1)8 v. C; j- X6 C, d) e% c
                {
  c4 ?; O# B! k  N) `                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!4 R( H5 V% N% x8 a) M4 l
                    continue;
/ H8 f  n7 j; v. s' _                }6 @3 h$ K" P. J) r/ i& J
                else
6 {( O. {4 @9 u# ~4 S' Z                {/ L& i/ z/ y+ P  i  g
                    if (numw[i] != 0)
; I* e4 x7 E( G" i                    {; s4 f* h* m# y0 |# A& A* v
                        i++;
8 O- d; V6 p1 Y2 m5 J, k- F. W                        k++;! ]# ^9 F2 R3 E4 x5 I. j" U! P9 Z
                        if (k == n)& _, ~' F/ T! q# s
                        {
  A( N4 c. Q, N7 V4 J                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 l9 d0 ?& L) w$ f1 C- ~
                            k = 0;
" \* [/ B9 L$ V9 x  ~* e3 T              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1/ M; `- t4 h% S  t  X0 ?8 J) s
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 X, l0 `. u+ v8 p/ t
                        }
7 V# {% b! D: F0 X9 ~                        else//输出暂时还没有改变数组元素的值& w1 V9 Y+ a5 |& K1 o
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);. C' L( r5 ]9 V8 K- F8 ?
                    }& g4 m4 N( o, ?) B6 Y) M8 H' _
                    else
1 |! C( y8 M, [: n+ g                        i++;//数组元素为0,直接跳过,不计数。。。& u7 W; M3 w1 ?2 l
                }
( w6 h& @( w; a% A , _& N4 `. l5 z9 y& m
, Y1 H7 ^# o( T0 m) H
            }//结束while循环5 _9 Y) g! t7 }
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦5 c6 x$ ], a3 e# H
           & p* V' a% h+ g" H# @; `
                if (numw[i] != 0)
" b- Z: L6 F: m9 `$ F                    Console.WriteLine(numw[i]);
4 N. Z$ O% J! f           
3 M2 c3 X* a# `            Console.ReadLine();
  {- {* b, }, p: K        }
1 y( {, V9 t+ @# n8 e    }
9 t% o9 H! Y3 K! a0 g8 v- H}. i+ W, ~; W5 t' @- |6 x" {4 z) t4 [
小甲鱼最新课程 -> 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, 2025-11-9 12:05

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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