鱼C论坛

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

猴子问题

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

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

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

x
大家好!4 N3 C4 E6 _. c* @4 n% b! t
这几天我在忙着编一个问题,我用了一种方法编出来!
& x: p$ S1 h( |$ ?) v! A# x- M但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!0 C8 {+ k+ l& s5 k9 X: Z' g7 o
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
1 ^3 C7 q* q$ }, o- f3 e0 D! S) s

9 M: `0 T; b. b$ @& t! W: R
                            题目
: ^$ }# @/ h2 j山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
+ f: U6 U5 u7 L6 o. h) b第一种方法:利用循环链表; ~2 z/ c6 F- m. @$ L0 L
#include<stdio.h>
3 |4 y& C5 A7 ~3 z#include<malloc.h>
# G- G3 o' x& x6 K( O# m9 x#define M 8            //共有8只猴子
/ ?. x6 m; A+ I# C1 `& Y#define N 3            //数到3只时退出第三只# d5 m7 d4 N. C2 g  b
typedef struct monkey
! p  P7 \* l2 @$ B{int number;& V) H* _$ A# F2 `1 W
int flag;  w  ], |4 p1 @1 V# \4 L& J3 R
struct monkey* next;
/ O4 k7 Q/ Y7 x9 ~}MONKEY;' h3 ], D( b% g- \; Q7 a. k; B
main()$ v5 C( S2 k! r; Q0 |8 I
{ MONKEY *head=NULL,*p,*s;
4 P! {6 `8 `; h4 m  int i,sum=0,count=0;/ Z' p9 `: w) Y1 O, f! V  t
  clrscr();              //清屏
, e% H" {1 D- I( T  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
+ K6 f9 M; I7 I0 h6 U8 F9 U8 Z  p->number=1;p->flag=1;
. _5 B, W* a5 ~! Q! v, I4 q  p->next=head;
9 Z. @" V8 a5 u  ~- C1 D3 i  head=p;
9 d7 u& h6 B0 K$ h  O* J0 y8 D9 _  for(i=2;i<=M;i++)% H- {6 M$ m9 D
    { s=(MONKEY *)malloc(sizeof(MONKEY));, M; @! C5 T/ G0 }8 V
     s->number=i;s->flag=1;0 X( U6 s, ~1 _6 Z* e# n, _/ ~
     s->next=head;
4 ~3 z: l% t! _$ h. u/ V1 U5 D1 {' @; o) @     p->next=s;p=p->next;
8 }* Q# l7 [' a/ J, `8 U3 l    }
2 ?" B6 |9 {% d& F& \6 J7 C$ @    p=head;0 y6 U- {" D0 y$ [5 a) C- `& c3 D  g
   for(;;)
3 l9 q0 c7 H# ]; E( o  F    {if(p->flag==1)
% S' l" x! Y" d: t6 k# S       count++;$ s; X. a: |; c- C5 ^1 p# n' o4 ]
     if(count==N)
0 W. N3 R' \) O9 Z& G+ F        {p->flag=0;: D/ i3 W- i4 ~6 N7 X7 D9 D
         count=0;
  M! q# F$ h- K0 a; \8 @         sum++;}  d/ _- P, H7 r. K* u# N9 I8 T6 W, F9 ^
     if(sum==M-1)
1 u# h& D9 R" n9 O        break;
% E! F) z  D4 Z9 x: l     p=p->next;
5 \  Z, t+ b* ^" @6 t; ?    }
- ]# |8 |3 z, U1 s    p=
4 w& h$ P+ K2 |/ y" k2 ?) B& z    head;3 [$ y( d. ~8 k4 Z1 B
    for(i=1;i<=M;i++)
2 [: [# B; B3 H    { if(p->flag==1)6 I6 T2 Y$ n3 s1 L
        printf("\t%d",p->number);
+ C/ G# b4 ]+ |- l4 V4 {      p=p->next;
  y1 c( \: d$ h    }
4 U3 S0 S9 b+ [& U) A- U+ e/ t
# e3 c) o9 [# t2 C# @4 a) }. Q5 l- B/ z
" x* l5 `1 D: h& J6 E
& T1 s, J- b) S}
6 Q, P1 B5 _! }
第二种方法:数组3 p6 |* e+ y/ @# v
#include<stdio.h>1 X8 F; h- F4 U1 s  G
#define M 8
0 I# t, b# q- k0 `8 c6 Astruct monkey; I1 R) X! q. P5 i% B; G
{int number;$ M1 Y4 b2 B- _3 J* e1 v
int nextp;
) A9 v2 h* K/ b+ V}link[M+1];
% J+ A9 T, _) R4 k: @* e& U9 S  ]8 K- C
( B; _( z; K# C2 R. tvoid main()2 M0 D# F+ r7 H" a9 F  a* @9 T
{int i,count,h;3 ]- ~. h- {$ f& i* R
for(i=1;i<=M;i++)
, \$ @2 h# Y! \# J: z, \2 Z{  if(i==M); G. O  z' O8 \* O
   link[i].nextp=1;  U: J4 k3 z0 K/ l0 g3 G- k; G$ X  i
   else$ k$ L# A% q" v6 S8 B6 d( l/ d
   link[i].nextp=i+1;9 a0 ]  @6 [' x, B+ o" ?( {
  link[i].number=i;
; z. P+ b2 U% C( b9 s}
/ H7 ~2 B! x: Y% ~# d7 I! M+ y; K4 Fprintf("\n");
) }+ W2 X9 a5 Y( w3 tcount=0;
4 l" o& C! p# R# Q7 s0 n# eh=M;/ T* y1 R1 k9 L9 n2 t% ^! Z8 ~
printf("依次退出的猴子: \n");& ^; l) W; H% N/ Q" L: Z$ |. t0 i4 h
while(count<M-1)
6 a3 O) k0 Y5 w7 _" x4 B{i=0;
3 N4 F- m# M4 a8 y. T; r$ ywhile(i!=3)
2 ?: h# q/ y1 a5 h1 h. @2 p' i{ h=link[h].nextp;
% ^8 v" g" L; `3 ~   if(link[h].number). C; _9 m- |) I& q
     i++;}9 b; q( {* A" ^: ]. M4 ?+ i3 B5 B; O
, b. s: q! q. v+ E: t& }
printf("%4d",link[h].number);- Z% y6 x: ]: ]2 l4 I1 m
link[h].number=0;# Y8 }2 t, m5 e, r6 l" V! E; [, n
count++;0 t$ G2 `5 q3 }) A' ^
}' h4 B) L% }. h! q5 O% D
' j, j' T" j, k4 H! P0 p' E2 E
printf("\n大王是:");  j& P4 `( r( x/ x  J# G# `
  for(i=1;i<=M;i++)
  N: j7 f& F6 C  if(link[i].number)! R+ n9 n4 V+ p$ c( @
    printf("%3d\n",link[i].number);
2 D7 `0 ~( W" |+ o
% b& V; m9 z4 I8 M% \, x, i; [5 R9 D# Y2 }
}

1 [! r) D: g5 l" {第三种是普通方法for循环

; R0 k' M& l" \$ K" W# p#include<stdio.h>
9 O. @. J  E  W2 A, y/ n7 D4 Avoid main(), t, e7 g! N$ l! }2 R) F$ Q
{ int i,k,m,n,num[50],q,*p;
2 ~7 O4 d- W, S6 ?# B( }    clrscr();
$ c7 l% H0 p) \   printf("input number of person: n=");! n. v3 H) Y+ s
    scanf("%d",&n);
9 z6 a& \: d& o1 z$ D$ t3 l: [printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只1 O4 M7 {* W. I. U' e' S
    scanf("%d",&q);% j! C* [, H; H: \- x1 y6 V
   p=num;& V1 ]1 D  Q6 X- ?! {3 \
  for(i=0;i<n;i++)4 y/ }, v: D: F% V" Y) p: e
    *(p+i)=i+1;
7 Y! p& M7 u. t. N% e   i=0;
1 d" `+ c4 @1 ~8 M+ j& G0 ]" n2 G  [   k=0;- C( s% m! \3 N& N( i
   m=0;
% G& m" {% o* o$ N( L/ o9 d7 A  while(m<n-1)
, Z5 G# w, T- x; B9 T0 [0 o+ P   {if(*(p+i)!=0) k++;
" [' q, Q% m; Y. j     if(k==q)
6 v- L0 G2 t, S* M: J- ?      { *(p+i)=0;
5 j% p9 F9 |1 e, W        k=0;4 Z& @; S* ?3 n3 Q# r8 T
        m++;
+ ?8 ?* `, v. T  L5 H! [      }4 Q0 T# w! Z9 z( D" w
    i++;
, b1 K$ K7 _6 h( t# x7 U    if(i==n)i=0;6 j' j' f& `7 e+ A, B% S5 ^
   }, ~) [% B8 a# }% K& l6 a9 R1 |! R
  while(*p==0)p++;
' q0 g, _" q6 f% O6 C3 S2 @    printf("The last one is NO:%d\n",*p);
) P% D" M" q3 R, i8 @' s     getch();) G. r' A* }# o/ j

' U" n, B& j. H5 K6 p0 {0 S% k}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
) ^( u/ P, ~/ ~) P8 F" Anamespace 又费马达又费电
4 C8 @2 d0 t: S" T) U- v8 `{
! l4 p4 V. M9 t1 g& v  Q1 V# y    class Program6 j1 u, E1 E! y# [: d7 Y
    {( X5 b3 r" U6 ^' l( u' w
        static void Main(string[] args)5 e# t7 U! K* L# W
        {( W. O5 P5 V! t8 r. ^0 U( j2 ^
            int m, n;1 Q& G+ u: }' f& @% d# R# K% }
            Console.WriteLine("请输入数组长度");
1 W' ?3 ^9 }9 X            m = int.Parse(Console.ReadLine());//m为数组的大小# I* ~! \4 `/ h& W5 Z6 ~
            Console.WriteLine("请输入要截取数字的大小");
, R. f+ F' E1 ^            n = int.Parse(Console.ReadLine());
9 |# x, r/ ?: M            int [] numw=new int/ H9 x& Z4 x4 b8 x+ G+ x
& i! }! Z  @4 B9 l* Y
&shy;&shy;&shy;;
' ~+ s: Q3 O% f            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
: O; [" q. m! b- q/ x8 j3 w            {
; Y/ K! I, r9 g8 c                numw[j - 1] = j;
" Y( |, W: U/ N- @* q            }$ f. [1 K) m+ y4 L* G
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!' V) U" `, f5 @
            while (d != m - 1)
/ h: K7 p1 V. G/ h2 l            {5 O* h7 C/ K4 z/ F
                if (i == m && d != m - 1)
# s- g& J. h! J  e                {7 \7 r* A9 A: V! w9 }
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!7 q# M: E5 V/ _/ a8 H3 E: v' D
                    continue;
. g; t! d% D8 F( e; H# B                }
7 S* K2 ~1 k: S: q; m* r                else# z: b6 \2 a$ i3 R
                {' y6 n0 Y, b% {
                    if (numw[i] != 0)7 J$ I. a  w5 v6 _0 u8 v
                    {
7 K* A! D3 l( i. E4 X                        i++;
/ S! Z& \6 o6 N' N                        k++;
7 c, v6 Z4 m% J9 e( u                        if (k == n)
, r. `/ N* U0 e5 o, q. x6 p                        {
- n3 o- N% O  `" V. Z                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
. m' ^6 x; ^7 G6 B                            k = 0;3 @; _6 L9 [# v( Z" A
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
# i3 j% F/ q- ]                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);% H# g9 [- \' w
                        }
* H6 v# u+ T3 w/ M! Y; H                        else//输出暂时还没有改变数组元素的值
! I: `# Z+ @0 a! w" y- ^                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
9 d9 r. Q" y2 U                    }# ?8 u! J) ~) [+ l) i1 J. c
                    else
+ ]- |. A. D& k                        i++;//数组元素为0,直接跳过,不计数。。。
- Z/ n( O' C/ H# @$ `! ~; v; w. t- F" O                }
8 d% r- w, c. z- i8 ?& ] 0 w) r0 L2 C: S) h4 m' j7 q

, J: [' `3 m+ V) h) L) Y! @            }//结束while循环" w! N3 v' @* f( h! e3 O2 Q* r
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦2 C9 X, I2 ^9 H( B& `6 m
           
) ?( ]1 ^! u% R5 n' _                if (numw[i] != 0)
& L$ r6 |. B+ K' w                    Console.WriteLine(numw[i]);5 o4 S3 m' R7 x5 w
           # v, [* w4 k" Y+ K1 U# T
            Console.ReadLine();
6 @' b* J3 ?# s/ u# ~4 i1 I' j        }
) G0 z% e7 N2 n" s# ^, \, ?    }9 P1 U  o5 z5 \$ [: O$ [7 ]
}
* Q& K( q* U9 i$ z) H& z0 J
小甲鱼最新课程 -> 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-12 05:43

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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