鱼C论坛

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

猴子问题

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

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

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

x
大家好!
1 w: d; n  z! e5 V5 M  l* V+ m这几天我在忙着编一个问题,我用了一种方法编出来!
% i$ Z% R/ _. H4 ^3 D但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
6 f1 y$ C, S9 w; p注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
% d+ B0 x. Q& u
& G4 r8 G# S: r3 g4 I% J) U* N! v+ {- \6 o* X; A6 }
                            题目1 S( k/ X* O7 g; w2 C
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。( M5 @; }9 l6 E! o6 t- \
第一种方法:利用循环链表
3 X2 E! ]* d: b& f' C: L8 v- V#include<stdio.h>. P9 `/ K( h5 X6 h1 D5 o: `2 o# E
#include<malloc.h>0 I# h0 L1 q3 {" n
#define M 8            //共有8只猴子
+ C4 v# A$ n  j#define N 3            //数到3只时退出第三只
1 @; H( a* b- Z, ?& dtypedef struct monkey
+ p" w: \" Q3 r3 n, n{int number;) v8 \: {  t5 L( e3 B
int flag;0 W. J: @4 \) g
struct monkey* next;+ g) A* O% z2 F  [& K& U6 e# ?6 F
}MONKEY;
$ P$ L5 Z! ]! s- y% j, o% _: w" Q0 kmain()
4 x: [& X0 P& `2 M9 _; q{ MONKEY *head=NULL,*p,*s;1 h6 V" o$ J2 F8 p. c( {9 ^. S
  int i,sum=0,count=0;0 Y9 {/ s5 z: \2 ]5 m0 u! d4 x) L
  clrscr();              //清屏
3 j& C  d4 S! U' ?' Q# N9 J  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存* Z/ ]* ~+ P$ S2 W0 |$ t$ _& O
  p->number=1;p->flag=1;: [  ]- F! Q8 o( _$ x2 @$ s
  p->next=head;$ D$ k5 Z6 |: |7 v8 B8 k; s) W
  head=p;
& p* z8 g3 m. h; j$ T  for(i=2;i<=M;i++)
& L1 p5 l7 o& S) K5 D    { s=(MONKEY *)malloc(sizeof(MONKEY));- E1 e1 n' b( V! Y" x
     s->number=i;s->flag=1;+ H# P! {* U6 J5 d& z: j
     s->next=head;$ H& J7 U* X' C; @5 ?4 G: \
     p->next=s;p=p->next;; T: _6 i  h- T9 J, n2 J" C
    }
# b: A$ ^$ K1 m" ~* w    p=head;
  q  D1 @3 j: N' e0 o$ D   for(;;)  _+ ^/ ]( K! U" j+ p4 W
    {if(p->flag==1)
9 |* o' }  N( q) z       count++;+ T9 `( L( a6 i* p5 Z( m3 q
     if(count==N)4 p# a9 i% T4 b; F4 Z
        {p->flag=0;
* f, q" A( E; y  Z2 s2 U6 P' k: }         count=0;
) d" }' Y" t0 S         sum++;}( s( d1 }/ b1 ]# Z: E* l  @
     if(sum==M-1)" h+ a  q. n5 H6 x# e* E
        break;
2 E- ~  x: t6 P7 v     p=p->next;/ g) a2 f/ F$ N$ s2 I; s$ g
    }/ L8 Y8 n& V0 \/ p$ I- ~" @
    p=: i' @3 ?5 K3 N, D
    head;
! b1 O7 D  ?. I: h" }7 W4 ]    for(i=1;i<=M;i++)
/ j0 m# t# U5 N" N  |* U    { if(p->flag==1)
1 g! D7 Y- K! W2 D) Y9 u8 l) S        printf("\t%d",p->number);# {# F  z: a- X, y2 M
      p=p->next;# u$ ?1 }; Y' @# @, ^
    }
; a6 H/ r) x3 @+ ?3 Z" ~: t% X
& \9 U. U8 O) V
2 H5 z( e) |2 ?6 G, u; e% ^- }, [, L/ \! b7 I- w: D
}

$ b" O) K: e/ E9 e3 I2 T+ a第二种方法:数组
- D3 ~% A5 B$ x/ Z. {' l#include<stdio.h>
/ x# W( C% j' i/ w- _& B( `" f5 q#define M 85 A( A7 K4 @( q3 z# c
struct monkey
8 w1 {6 F: j+ B2 J0 q{int number;
8 o5 B& h, A& Y/ g) wint nextp;0 a1 ?! N- Q( y' d, d, k- `
}link[M+1];
/ o# d+ R$ U& N6 c# _. A% a& `+ N
void main()
0 d5 Q$ }  ?+ |  b+ f+ G{int i,count,h;: Q$ ?5 @- X8 G  |4 y- |
for(i=1;i<=M;i++)- P: b" l) V9 @7 j  k: ?, ]! j
{  if(i==M)$ r3 Z7 k/ A- S9 R' s$ Y
   link[i].nextp=1;; z: q/ K' n- l: V* j# R! w( c3 A& d
   else& o, o/ ~6 ~. R' I. |
   link[i].nextp=i+1;
, o2 |( S8 R) R$ O  link[i].number=i;: P* s+ _# D4 a+ G! J
}
. N/ C& T8 N+ M$ A) L" x! wprintf("\n");% y+ e; A$ e" ^" t2 T$ N0 t3 u- M: a
count=0;" x" j* m. D+ |# b/ \& m
h=M;
$ t; @1 Z6 n% o+ d3 [- R) m9 @printf("依次退出的猴子: \n");
8 `: C  J  X8 jwhile(count<M-1)
+ W2 s  ^* c* f. _( ~{i=0;
* t) ?) l! L6 E) N& _) ?while(i!=3)
( v) n9 P$ f* y* G. T{ h=link[h].nextp;
% g5 H9 {' Z9 \% L" h; D& K   if(link[h].number)$ b8 H% c, D( e4 _$ V) }; I
     i++;}2 I* _# w2 N: @* S9 ]6 p7 y
, E9 ^3 f! v1 }/ O* a! Y* ^' x
printf("%4d",link[h].number);! K3 k: \1 ?0 e9 _: c( ^
link[h].number=0;
0 _) n9 }; J) K% F3 rcount++;, W, B3 K1 d' R2 R$ o5 f+ {  [* J
}
* V7 c' p/ D; M1 J* W! x5 M' A2 _- t8 q* g/ X7 a# k- I. q
printf("\n大王是:");9 g# Z( [2 c2 E2 V5 O
  for(i=1;i<=M;i++)3 L4 d' E# _7 C4 ]9 Q
  if(link[i].number)
. A" a: N4 r+ ?% T3 e/ z1 M    printf("%3d\n",link[i].number);, s4 y4 D# B' q, w
4 g9 ]& r" {: {1 y7 ]2 O

/ E3 w& g3 D) i}

' N. D% I2 Z  i% N# @' q7 _第三种是普通方法for循环
  \* g$ J  y: W# ^( N5 F7 x, w# k8 [
#include<stdio.h># \8 j4 j( l* @) U
void main()
' Q) B( [; T+ K{ int i,k,m,n,num[50],q,*p;9 O' {. {0 `2 |) T: P
    clrscr();
2 A8 d  b8 l  w) z+ @; l$ T   printf("input number of person: n=");
  r1 c0 v) D) L  C; C: a3 {    scanf("%d",&n);
4 \* X7 `- {7 t% c' Yprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, U6 p: J' c/ k& K+ ^" E$ \    scanf("%d",&q);( R1 F) h8 T5 I
   p=num;5 J1 G# t. X3 h" l6 V
  for(i=0;i<n;i++)/ l; A* r- s0 w7 M1 Y% K5 N- |9 V
    *(p+i)=i+1;
4 v1 Y) P- b8 e  l" j2 ~   i=0;
2 d" C; P9 M1 r/ V3 A; f8 x   k=0;8 y7 n. d! k7 K
   m=0;
' x5 Z9 ]9 Y9 o% _  while(m<n-1)
) U( {, B! g- K* K3 E& g1 S   {if(*(p+i)!=0) k++;
0 a5 r1 u5 d9 h5 Q" i! c     if(k==q)# }3 ~& Q+ I8 z
      { *(p+i)=0;& F. u7 Z5 _1 p" h+ a! w  H
        k=0;
% l. l: }5 {8 C6 x        m++;* O1 q0 V1 _% }4 W
      }
+ C  x, N! @! ], ~1 l    i++;
+ F" r0 ?, ^) C. ^    if(i==n)i=0;9 t" @& f" }. ~, |' W8 \
   }7 [8 ~" G+ m' W0 o
  while(*p==0)p++;$ w9 q& b0 u$ ?+ H, i
    printf("The last one is NO:%d\n",*p);1 b$ f& ?5 h. f9 y% B7 E+ C8 ~
     getch();2 P, x, ]" a! V9 y) W0 t4 G  ^2 I( c

/ T: M: `( B- p, ^! J/ ~$ m% G}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;7 K" v1 \. L7 r* ^. {5 R& y
namespace 又费马达又费电
- X0 b0 X! q& K+ K{
1 ^  T4 w. \8 r% p4 B    class Program% `# H8 C2 X& S4 U; _& E4 T
    {/ X+ {% e' d& x
        static void Main(string[] args)' N+ F4 ^+ h, ?5 N& P( ~
        {
, D& z! m6 p" w0 E            int m, n;4 u) v3 E' z" O
            Console.WriteLine("请输入数组长度");' S4 \# g! {6 o7 n3 f6 M! Q5 h) e* _
            m = int.Parse(Console.ReadLine());//m为数组的大小/ }6 ~. j8 c2 @" O. n5 T5 R! w, p7 t
            Console.WriteLine("请输入要截取数字的大小");
8 C3 Y1 l: k. O2 {1 B            n = int.Parse(Console.ReadLine());4 Q5 y  S( Q( P
            int [] numw=new int0 `/ E% h+ L- l$ t
5 X9 H8 X% w; N/ s3 Z9 e* K. w. m
&shy;&shy;&shy;;
, L) E1 L5 A% |+ a) `3 k. C) V4 y            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
5 R% h) M" a" W            {% k2 O) p# p; k; ~! L: p- Z  w  @
                numw[j - 1] = j;% _6 _$ I" g0 M  {, B* h
            }
6 M9 z4 F4 k( c: u            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!* J- N/ w4 w" D+ \- W2 a, s7 ?
            while (d != m - 1)' w$ V* e. A- g! N( G
            {
" I( o% e  a9 x& [: k# E1 ?                if (i == m && d != m - 1)
/ m1 v/ ]7 o1 h0 z                {
1 z  y. g% a( |% p4 W( }                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
) e; ?& Q( E6 X                    continue;
6 a5 v* d3 V. V% D; [" Q& b9 A4 k                }
* I1 Z& C$ `1 Z) Q9 P                else
/ I! \/ W# i9 C% A                {
# R3 [8 ~$ T) I. a. Q8 d                    if (numw[i] != 0)
/ s, \9 U) ?  e) S& L$ L; `' J- l                    {
! E, ~/ v2 V$ Z7 P; ]; Z                        i++;. W) p% h/ L& \( Q
                        k++;9 E2 @% k9 ?4 ?: ]. M
                        if (k == n)& H6 C  i* Z# X
                        {
' s4 b" l- Q( F! i                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
( b! t5 t, W7 t4 s- r1 |5 f% l. z                            k = 0;8 M9 {3 Q% \3 f0 l$ a1 Q
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小16 u$ [& o0 ~$ v+ z  G' D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);- o2 Z& y* e: Z* B! Y* n# T+ d
                        }
# N' X! N" r' o* U) D                        else//输出暂时还没有改变数组元素的值
& v8 b# P  G8 q& S9 I+ D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: I/ [6 ^  v$ J5 U
                    }
$ [3 {) L5 B/ V7 w2 t- O                    else! m; O! B; T1 O  L& l
                        i++;//数组元素为0,直接跳过,不计数。。。( l& i- F- b; @" g- u6 r
                }  G! H9 |- ^( N! Z: g$ A% {
; x* z2 C+ V! u0 ?! ~6 v- N

0 j, E  c/ C/ c" ~7 f+ ?3 W7 F            }//结束while循环2 I. t4 d* z/ |1 ~
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
0 d3 k$ e' r7 P' i; M# C           / Z! [0 F: n  P8 H: c  {# s" j  z
                if (numw[i] != 0)# S9 h! l+ N  k  u; w
                    Console.WriteLine(numw[i]);
/ F! p0 a: ]; r- d: R+ j           6 h& n6 c8 ~4 M# O3 m& N! I" U! g
            Console.ReadLine();# _2 p8 l3 _% L) F7 Q: f- `% m
        }
1 G+ u, i" k( N# Q& Z/ y    }$ |  J, y0 Q; \  X5 U9 O
}
& }8 h$ |  T* {" {+ m$ ]8 p
小甲鱼最新课程 -> 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-2 07:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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