鱼C论坛

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

猴子问题

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

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

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

x
大家好!
; m4 m+ p. t% w6 d/ H0 y这几天我在忙着编一个问题,我用了一种方法编出来!
! d8 b" y% Y: o- Z7 ^但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
& I& V7 E; i" V! z4 |) P注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
, G& L$ Q2 G) ?. Q( w: Y1 b  h1 y6 h7 L
! @- ^$ Q8 h1 Y1 b
                            题目4 x0 s0 e$ H. ]( r( q
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。7 q& R7 e* I, `+ P0 q
第一种方法:利用循环链表
- C6 P. p( [# d% E5 l#include<stdio.h>
* c  v) {; R8 [0 v5 }" [#include<malloc.h>( g/ q  Q9 W2 r7 E! W
#define M 8            //共有8只猴子
6 B& M& Y" _0 e  O0 b#define N 3            //数到3只时退出第三只
& @  a' I- p: S) J7 l9 jtypedef struct monkey( N4 e4 D/ f: `
{int number;
# f# O4 c% T8 I# s1 A" Gint flag;
+ f9 t( G, C* j/ {struct monkey* next;
- ]0 U/ G* H- \% ^( O}MONKEY;
& i* c5 {8 f, p( m3 E. m  z! mmain()
4 p% R7 }" w( {" @4 Z0 G( M, _{ MONKEY *head=NULL,*p,*s;
0 n5 h. R2 g) d( U, }' x  w1 v  int i,sum=0,count=0;
0 X1 _: G/ h7 }% J/ w" c7 ?  clrscr();              //清屏, c, _- m( H2 F4 l
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  M' N1 n1 \6 l1 A+ D# ^  p->number=1;p->flag=1;5 H. S2 M2 Z. s' {% c( F% g
  p->next=head;
$ M$ u7 b6 R8 N4 m4 k- H  head=p;
) O; Z; c. q$ B0 c  for(i=2;i<=M;i++)8 n" Z4 l1 B8 V+ \' ~7 |2 Z
    { s=(MONKEY *)malloc(sizeof(MONKEY));
' n# G/ [# E) R2 A' S     s->number=i;s->flag=1;
' O7 \+ ]1 `0 R     s->next=head;
: h. ]& x- r) D2 G! N  k6 R7 [6 _     p->next=s;p=p->next;
8 f+ e+ {0 k# }" ^  _1 w7 ^    }
1 h9 p, ?; h* ~3 u4 F6 T    p=head;2 Y( ^+ V/ C% B
   for(;;), e! }2 l% j: n& S8 N8 y4 ~7 W! B
    {if(p->flag==1)
! a* W2 `% H" @  c* X; K+ m2 d       count++;
+ B6 Y0 k$ i. N" j     if(count==N)
' S; b- w5 n6 k/ @0 L- E2 S; w        {p->flag=0;  V) j$ \* P3 g/ [
         count=0;! G  `+ e" _6 ?3 j, Q% n  q
         sum++;}
0 R: L9 r* x; ~- b+ [' e0 a6 N     if(sum==M-1)5 I# O3 ]/ i# S# Y0 W( b
        break;4 ~' [% A' b; w- }. R
     p=p->next;# x% j2 d" Z+ L/ ~# [) `
    }
5 b) x" @7 `1 H. M5 e! l    p=
  {4 [: H" A" _- L    head;
0 F/ r# h  i4 k+ b6 _7 L: z) |4 i5 f    for(i=1;i<=M;i++)
  u0 c# ^' J+ s4 V    { if(p->flag==1)
6 Z8 h* N, k% w& B+ _0 K/ q6 Z        printf("\t%d",p->number);$ r# V# k2 q4 ^  l1 ^
      p=p->next;! H2 S4 v8 J& F* X5 z
    }
# e: S1 x5 u! R) g+ Z2 x# z8 y. |0 C3 }6 @2 g

/ L, r% H; {7 k+ _# y3 b8 Z6 {. }. F  \9 d0 N
}

2 o1 [) @5 K' E: s" A第二种方法:数组5 [4 }: S* H, T3 g9 C5 x
#include<stdio.h>
, h& k' }4 Q9 Z#define M 83 |$ b3 ?# ]  o, T- a# Y8 m
struct monkey
/ B1 D/ i5 {6 Z# n6 i! K! \. z{int number;1 _# q3 a1 Y. ]4 {5 [9 N+ Y
int nextp;& O& m9 s% ~/ T0 J# N3 k
}link[M+1];
' h1 q  O" @7 ?) @0 [
3 B% W; k$ A+ e* h* `3 Ovoid main()8 G5 h& T% D/ Z4 Y1 L3 i
{int i,count,h;0 x8 [. n% y8 q& T
for(i=1;i<=M;i++)
$ F4 Z! d1 H' G- s* y{  if(i==M)- ]% t& t2 J, r! V% S& o' s
   link[i].nextp=1;
8 P) @5 V! f/ A& k9 r8 T   else6 J$ V* r7 L; D7 D: U: Q- r
   link[i].nextp=i+1;" P: r% C0 `7 K, h
  link[i].number=i;: ^3 r; ]* [. T7 g
}
- d, V& l5 d, F9 S/ Z& J7 E* m9 l7 kprintf("\n");5 H8 c( k$ ~7 t; \
count=0;
# n' n; Z6 @- w- b- kh=M;2 c9 u8 P7 d$ w
printf("依次退出的猴子: \n");
, a3 j- c* u  f5 d0 Q. E8 y- L" xwhile(count<M-1)
+ q- M" d" Y" C9 a6 `3 j{i=0;
" \6 K& E$ C- l6 ]. hwhile(i!=3)
8 @1 V$ k+ P0 A. F# }{ h=link[h].nextp;! D% Y5 }+ p2 m6 g  r
   if(link[h].number)
$ G' O- t9 _7 T- `  r1 W& ?0 [     i++;}
+ r9 \/ ^- x9 p2 a  D3 b& B& i& S& X" ?
printf("%4d",link[h].number);6 S. V! u* L% m2 ]
link[h].number=0;
& K" q# D1 }5 D. [count++;
/ H: R: ^/ z8 d/ W}9 J4 A5 K9 b$ N

# f" w  a% R9 B4 mprintf("\n大王是:");( [. `+ o2 ?( @0 m  D  M
  for(i=1;i<=M;i++); V& i; h+ H( g! @( M% I+ g
  if(link[i].number)) u3 o; y; F1 h/ F
    printf("%3d\n",link[i].number);5 ^1 S- Z8 A3 Q- ~# Z% k* m$ I
1 K3 ^* e: B& F' j
5 `3 l( a" d" h& K" u& u
}
6 _* L/ }0 N2 ~. n" M& _: U; E
第三种是普通方法for循环

/ T! Y$ {& g( n2 A6 F5 S1 I#include<stdio.h>
1 j* H1 B  G( Evoid main()
; I* |- b9 d% A$ c  H{ int i,k,m,n,num[50],q,*p;7 d! h1 L  j* X. M9 U& m, A( D8 X
    clrscr();
, ?: O0 Q0 I7 @8 S9 ]+ X   printf("input number of person: n=");
# M& J4 s3 c# S! r8 C1 A( Z3 u: ?    scanf("%d",&n);
: j1 g- j* P7 l% a9 cprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只. y# u) F( F1 c: q, I9 f
    scanf("%d",&q);; Q6 B" p2 A5 C
   p=num;
6 Y/ ?' T! k) d; n! |3 L: A; G: F  for(i=0;i<n;i++); S* Z* y  C( _& F! W+ f
    *(p+i)=i+1;) C- H8 `' s, G2 I& G! P
   i=0;( d& z& N6 t0 L% Y
   k=0;
; M/ H3 |+ Q- ^' m4 `  L0 K( q   m=0;
8 r# Z- _! u) u) ]  while(m<n-1)
. e7 h) m/ V/ N+ n( \2 K8 M   {if(*(p+i)!=0) k++;
, a  t8 t8 ~. c# w2 r- P     if(k==q)
5 M/ e8 e) }, L; v  E5 k      { *(p+i)=0;* e6 G" Y: t+ |1 i
        k=0;
5 w( w9 ?! @; C* u        m++;% X  q( h" s  J0 @+ A) G' `
      }
. V7 L% B5 z. r3 ?" }0 R, S8 x9 H    i++;
$ C8 w- V$ _% N& I) x+ B% o% z/ F    if(i==n)i=0;
3 H+ g0 o5 X' N  Y! R. ^( c   }
0 `7 g8 B1 I+ r+ ~! ^  while(*p==0)p++;
; P  }5 a7 J! v. Y& I4 U    printf("The last one is NO:%d\n",*p);' Q- @. C6 Z' O
     getch();
* K3 }! Z* H: O. A! x
9 }: E# }; _& N, g  H3 u}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
& \& B  q; X/ |1 ~( unamespace 又费马达又费电
" x' V, u+ C: W' b{- l7 m4 P6 A1 F/ a6 z/ G
    class Program3 e8 z( e$ g( Q" }
    {
& h$ K* c; `. z5 U* o# s7 O        static void Main(string[] args)8 {9 D) y. v' K) s* l
        {
. U  g* f# i% P4 T$ D            int m, n;! s* q; w# K  V! c
            Console.WriteLine("请输入数组长度");
. q' {# v# _9 L+ p. L. ?! h$ Y            m = int.Parse(Console.ReadLine());//m为数组的大小" v0 f. s) Y# u$ Q% X1 m
            Console.WriteLine("请输入要截取数字的大小");
4 N, b& O" G3 C            n = int.Parse(Console.ReadLine());& N& \5 I$ O; L; y0 ?1 \! I. X. c
            int [] numw=new int
0 J; s7 A) d, r" X- `
& o( }6 O' P* V  X# J5 l- A# \&shy;&shy;&shy;;8 `# M; s# E7 J% Z6 g, F; e+ o
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
* H& v$ D+ T# e% a            {
! _9 i7 B( l1 Q- A$ u" ?* q                numw[j - 1] = j;) W4 l  x/ H4 @1 ?' D1 x% b3 ^
            }+ ~: \' O2 F6 ?
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
+ E; n( Y* d% a( J. b4 s            while (d != m - 1)2 F3 L4 L/ @3 U& H! ^0 K
            {
% l  W) z3 h, I" V                if (i == m && d != m - 1)
' h) ]. Q( q5 l" E                {1 v0 l9 s3 W/ F+ v
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!8 P( R  W/ v0 F8 o3 x4 |
                    continue;8 v; u/ n6 w! B0 t" q
                }
& [" @- a: l$ J* O                else! [9 D& V7 S8 q
                {& t8 \& Z* v" a% \0 `  g
                    if (numw[i] != 0)
; s/ U/ j3 P( }$ b  r/ u                    {# u& U5 F9 j0 k
                        i++;8 Z0 k* h: h- m/ q7 [
                        k++;) k) o$ p% J: f" p  l+ R; r
                        if (k == n)7 G  c# g: m& L
                        {$ _' J8 ~5 T- [% i1 T, b4 s) Y
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了/ i1 q  A2 u7 q1 ~7 v& `+ z
                            k = 0;5 r' B2 B+ a! i+ p5 K
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
6 `6 e; l0 b6 g% v* x                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 \5 g3 y1 H* {: g6 D) e( b6 o
                        }
! Q, _0 K" ]4 R: L* U                        else//输出暂时还没有改变数组元素的值( f# E5 q/ V) n: R1 K. ]! M( g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
) ]! J7 J! _+ v$ U/ h                    }3 [5 ?( C8 r- K2 h2 k$ E
                    else
; l" }" w: A8 Z! }+ Q                        i++;//数组元素为0,直接跳过,不计数。。。
- w3 h, g9 x9 Y5 D                }
: d( n) ]/ @( V7 ~ 9 V4 J! }$ E6 w* |/ p; x6 ]; X

; l- f9 `* l4 }5 g: j" C            }//结束while循环
) ]( ?' v0 o% R$ q            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦- ~. p% g& ~: Y' c, J6 k' W
           ! g6 u  M$ @3 q) O
                if (numw[i] != 0)
  Q% _+ r' r! F& a7 I* \* g9 H                    Console.WriteLine(numw[i]);
) v% f* G9 n* w: m* Y           
4 @. h% N/ ?" _- R            Console.ReadLine();* {  C9 x; O: t3 g- i' ?: w
        }
5 i: c9 e: c+ j. A' ~6 w0 C    }
/ d2 C4 f+ S+ B1 z0 J- r: E}
- e; g5 V* M) 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-4-8 00:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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