鱼C论坛

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

猴子问题

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

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

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

x
大家好!
8 i+ o8 @9 h) P0 A1 X; k2 o这几天我在忙着编一个问题,我用了一种方法编出来!
' @. h; x8 a5 H9 [& v但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ x3 T% t/ q. l8 u$ E% h
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 ; Q4 E+ [4 _' |
+ |& y/ K. T; y9 k1 _. \# b

9 n& W# H6 z1 a* R* S8 C
                            题目
$ v# j/ a$ ?+ k" `4 E0 x' m6 c3 X山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 m- a' k, E* c6 J3 M
第一种方法:利用循环链表
; n( R' S7 U4 ?#include<stdio.h>% C; M1 [6 L1 {2 |! f+ B. x
#include<malloc.h>/ l5 {4 p% B' i  `" c" ]8 p2 a: D' l/ w
#define M 8            //共有8只猴子
$ y* O9 z" P" {6 @5 d. Z# w1 j2 ~#define N 3            //数到3只时退出第三只$ H7 v. A7 z. K; F" ]0 g
typedef struct monkey2 \8 N) K1 k9 s$ A, N# C# {
{int number;2 b- V: s2 ?- `7 X  J" @' ?
int flag;1 k+ f( g' d$ a# ^7 G2 C3 Q5 w) G
struct monkey* next;2 m5 |, f* Z2 @" p
}MONKEY;# R0 S+ U% i9 ?: ?1 s4 U* D$ L, I0 B
main()
9 p( `! Z! Y, m/ e/ a% o. u" V  f& ?{ MONKEY *head=NULL,*p,*s;; I7 e9 J9 ^; Z5 \) x6 O
  int i,sum=0,count=0;) o, [8 \: x% D/ s) _
  clrscr();              //清屏
( d. J" Q! K8 L. `8 `  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
8 K0 m5 o, ?1 }, Y, K( y  p->number=1;p->flag=1;
5 D2 y+ m) [# Z# a5 C1 Y  p->next=head;: u! l7 R9 {( N; ^& C( Z9 K4 R6 M
  head=p;
+ |) m. I/ K! @( @/ P  for(i=2;i<=M;i++)7 t0 d$ t4 [5 S" Q+ d# q
    { s=(MONKEY *)malloc(sizeof(MONKEY));
2 i: G) S% _' d8 ^: Q3 w3 `' @0 B     s->number=i;s->flag=1;
1 S- ^% ^- M& Q" s3 V: h5 n% A9 J+ R     s->next=head;% s# Q4 X' s7 v# W$ P/ P9 P' w
     p->next=s;p=p->next;5 n8 W/ D; t/ g: M; V7 q1 G
    }! J4 a7 q5 h( T+ ~7 z- S* A
    p=head;
! }8 V2 ~4 h; i* r   for(;;)
# @0 f. k5 j2 [% n    {if(p->flag==1)0 R8 t# G! e+ x: z. _2 @
       count++;3 }; {3 j8 u& P/ h2 O
     if(count==N)
" L4 K! [: k8 ~6 E/ S        {p->flag=0;! \, {2 {! H+ p' @6 S7 p* d1 i
         count=0;# l  f; |/ C$ Q8 W. Z" X1 b! U5 ]
         sum++;}
0 @$ y+ s1 _  j  r9 U& H& s     if(sum==M-1)
( d( ?) m3 C+ i% l+ n% R        break;
# P  [) C+ w* s$ m, h; n     p=p->next;! m! D, m6 E% }+ L' J1 |0 u. ]' ~
    }2 F4 y, i: r/ G, {- r, J7 K
    p=
, m- n$ k" j$ Q! T- Z) B    head;6 U" R# ^4 b" l+ U& }1 A1 Q
    for(i=1;i<=M;i++)
2 X1 H4 @  C) ?# R$ `    { if(p->flag==1)' L- h4 ]( ]' O1 Q# x8 E
        printf("\t%d",p->number);' Z# l2 ?+ y2 r( P$ q
      p=p->next;% F+ t' P$ Y$ d  r: C0 F) B4 M; r
    }5 c0 k( h4 a' G3 U+ E
2 `, p1 J" W8 b' f5 P

  S  B& R; J/ B- i" H! f+ A+ u! {
}

! l% V/ i/ [+ R2 U$ {$ z( E( g2 R3 K第二种方法:数组
5 ?: S/ H0 f5 Q' V. a8 b4 ~#include<stdio.h>$ R/ b2 Y* ?, ~" I9 p- G" F
#define M 8% W; y5 `- ?4 ^8 L+ C
struct monkey
* I! w/ c* g& c& E1 W{int number;/ i' @0 b+ d$ \
int nextp;
* c0 \# p5 P8 D5 Y; S0 O" ~}link[M+1];$ ]8 `( ^% M& i' W# g$ G1 K

+ ~/ d8 m9 @* m8 D3 I$ nvoid main()
; b- E& e- f* c& b{int i,count,h;2 j/ W/ b: E5 M* R5 A) R" |
for(i=1;i<=M;i++)$ [. d+ ?3 Z2 z2 V% h" H  q
{  if(i==M)* f# F0 |3 x/ _
   link[i].nextp=1;8 S4 G3 ]- G* j; k
   else
, l9 W2 Z! f& d   link[i].nextp=i+1;
& l! p: d( Y# L* e8 R+ U  link[i].number=i;' H+ y- M2 U" L' G+ \/ ~
}
& p: x$ {% l! q( Hprintf("\n");
" V  P- q0 k/ ncount=0;7 Q4 e+ ^* Q% t8 V
h=M;7 W' i1 v7 j/ `) V
printf("依次退出的猴子: \n");2 r5 @7 K! W6 e  J; ]; h' i
while(count<M-1)' }$ S0 q( z5 H$ J: ^# h
{i=0;
' `% P) b% K2 f9 m0 ^$ ]while(i!=3)
/ @' J6 p) w4 z8 F5 {3 F/ X- b! ^1 q{ h=link[h].nextp;
# J4 M) s  O& [/ g" ^7 V& T   if(link[h].number)
2 ^- f' k' L. Y6 C: t2 \1 {     i++;}# Y: m% }+ e# K! K

, ]+ d. P  M$ y% R9 Rprintf("%4d",link[h].number);% Q, w0 n, p3 v# W% b( J
link[h].number=0;
& B1 K: B2 ^2 s% rcount++;
& q/ \& ]$ H$ g2 G; N' r2 @; H}8 d/ }; T$ P) F& L4 E5 L8 Q
2 U( ?* V6 b0 ^9 b& I- {. _. N7 h
printf("\n大王是:");1 U, \) q& p* L
  for(i=1;i<=M;i++)
# w. X* N/ r( g* c% Q$ g! l  if(link[i].number)6 j& c' {7 P3 S
    printf("%3d\n",link[i].number);: H' E$ z1 ]2 L+ ~

- i; K9 s+ Z& M) |( e& j! ?( u4 S' b' U
3 B. k: r+ _+ t0 ?/ m) K}
) D' V+ Y# W9 C+ `% E
第三种是普通方法for循环

5 k: b: T! |6 n( \! U$ y#include<stdio.h>2 m( k6 `: N% \* R
void main()3 V. J: v5 i) P" g  Z4 r. g
{ int i,k,m,n,num[50],q,*p;
# E& `  O7 Y0 ^4 @  S    clrscr();1 }( Y0 g* V- b. s
   printf("input number of person: n=");( y/ v6 J6 C4 Z+ u7 c5 R
    scanf("%d",&n);5 L  f! I3 I( Q+ B2 x* Z+ t" J
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% S* f# {; l1 [% O& ~, _
    scanf("%d",&q);
0 \, D% x8 _& d4 N" N* H3 C   p=num;  m( U+ i( f1 y# o( c
  for(i=0;i<n;i++)* Y1 O6 B4 {$ ^# {$ l
    *(p+i)=i+1;* Q; i5 a0 N. Q0 o! B/ v
   i=0;
, S  N3 o; x" \$ j   k=0;
3 |. X3 P7 T2 {* i5 |0 g  t- {8 E   m=0;/ R* Z, |$ b, v; S, F
  while(m<n-1)8 Z( c0 n: |! k2 a1 ]; t+ @8 ]( P
   {if(*(p+i)!=0) k++;  S% @5 O. o) B, o& n' E
     if(k==q); o2 E7 X9 e1 M* m; \
      { *(p+i)=0;
$ d4 H2 S7 [: y  q% ?        k=0;
8 ~2 X2 q' ]: V; k% @* y        m++;
) R# D) c& ?4 d      }* W- Q; O8 `' W! p) ?
    i++;
4 T8 ]3 l4 q6 c: [; h# e    if(i==n)i=0;
7 R1 n  Y7 ^( P5 x& g, B2 e9 h   }/ o  a% |0 O& x* R: i) M
  while(*p==0)p++;5 u8 X( A, S8 Q4 C
    printf("The last one is NO:%d\n",*p);7 V  V7 c) `' j6 A' }5 v" t
     getch();
) O2 D) A) {& G
& X# k! O! I5 b; L4 |7 K}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
5 H9 U6 P) g$ R& W% _  Znamespace 又费马达又费电# [) J& C7 Z: C# d
{4 j% p9 U  d! ^; ]# S: t$ Y
    class Program0 D; s3 e9 r- c3 ?9 G
    {  ~2 i/ u) W- y  p& v7 v
        static void Main(string[] args)
: t6 E' ~9 c9 s- h        {, Q$ x9 u5 n8 [4 g3 l- s
            int m, n;: `7 \4 `4 s! g+ A
            Console.WriteLine("请输入数组长度");
6 }5 m/ ^  l/ s6 S6 A/ s8 S/ l8 _            m = int.Parse(Console.ReadLine());//m为数组的大小! |/ ^6 v- u$ r$ R+ m( L* R9 G& J& n
            Console.WriteLine("请输入要截取数字的大小");
, G# x9 Q- q6 k) T3 @. V# f            n = int.Parse(Console.ReadLine());
9 ~- L/ k) a2 \            int [] numw=new int3 a* N  }; L. o9 n! c
+ q* |  U) J( f6 q5 G" [$ b9 ^
&shy;&shy;&shy;;. o- e- q% j0 O# N4 D
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数3 g3 C# ]1 K6 b. X
            {8 @9 p" x$ Z% o; w) b
                numw[j - 1] = j;
& s% z+ @; i5 N, m! L            }' R6 x; U; v' q- X) z# L
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!* g+ P" q7 i, |4 m3 p, H& H" B% x
            while (d != m - 1)
- d3 i- }' F; E: {: Z7 d5 B            {
% a% r! e/ f* C( n) K) V8 n$ x" z                if (i == m && d != m - 1)/ m1 m2 O% \0 ]! r
                {
7 T1 `% W" Y4 b+ {8 M) z- B$ O                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!6 ~" R1 I* ~  g; }& t1 f! w
                    continue;- }. i, H  N% w
                }/ P" K0 Y4 |* d: C$ W8 a. H2 Y# x
                else
0 Y/ q: z1 ]6 T5 h4 n/ j3 S, t                {
4 k( c" X$ t; ]' c                    if (numw[i] != 0)
  Y- a. P2 L: a$ Q' w0 a                    {
  r6 ]4 @$ I4 V' `' z                        i++;& Q( A) @2 |7 Y% y
                        k++;/ a  c( V( f( B
                        if (k == n)
+ N  H/ I& O# _1 b% r                        {
7 a3 x0 l' E# s. V9 S  L7 C                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
- [  J% v! b- L3 r( f1 D4 }( a                            k = 0;
, O0 Q7 I; E( P1 @              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
/ e1 u1 D. S4 s, N. t                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 N6 f- v( m" w7 Z  A7 K                        }+ p5 z; t1 p; m, n& }
                        else//输出暂时还没有改变数组元素的值& o3 U3 U! o: O+ M# x" R
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, ~( U$ n4 R6 C' e5 R* I                    }
, y4 o! f: R3 J, @! z2 O                    else- s% y/ U1 _. N: O4 Z* C
                        i++;//数组元素为0,直接跳过,不计数。。。. ?9 L) u/ k" X2 D& H" I
                }
) }  u! B' |2 v( G3 g& @ # g( M2 f' t$ S$ m, {  [* F
( T, [0 e. F' M1 f& [
            }//结束while循环2 @3 \8 g( z5 K$ h
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦1 }. i" G: T, \% _- @
           
1 q$ E# [1 m6 ^* [& l4 Q2 [/ z                if (numw[i] != 0)
6 X2 P1 a7 k& O( O5 E: O                    Console.WriteLine(numw[i]);9 |, K( P1 e' n- E" w
           $ P, `, L0 G- s) {
            Console.ReadLine();5 y  u) t. j+ u9 Z9 r( X3 _. k
        }
& G4 r+ R7 e% y/ k0 d    }. g0 w; V3 g, w9 w& x( n
}3 u4 Q5 g3 d. n# ]2 t4 s
小甲鱼最新课程 -> 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-28 19:13

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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