鱼C论坛

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

猴子问题

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

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

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

x
大家好!
* x4 k5 m: y2 n4 ~! x2 q这几天我在忙着编一个问题,我用了一种方法编出来!9 Z& q" G; Y- O% N
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
" J# U8 K. X, M# n7 [! u+ b注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 - l2 q0 B) [4 m' G& ^+ W0 |; ^

, n9 R+ ~; ^: S5 r  m; N7 G2 P" R% c" a. j' {3 f/ Y) z
                            题目! z; p( Z& A  D
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。, p1 A) n0 M! S3 ]# H" {% e2 s# x
第一种方法:利用循环链表" Z" z/ d  x4 p* E; y5 O
#include<stdio.h>) L- j8 ~% q$ g: h9 X" D
#include<malloc.h>
/ H1 L9 t. s% Z; d+ E" C9 ]" l#define M 8            //共有8只猴子
7 r/ f2 g0 q  Y( T' B8 V6 p#define N 3            //数到3只时退出第三只
* u7 V0 a" R, d! d2 [typedef struct monkey
1 E1 B* }% q  }# Q* p6 \- c8 D{int number;0 R0 R# m- u' `" e* b
int flag;
. ~6 d$ F5 E8 r1 s% f$ `% }struct monkey* next;6 o. p( r' p1 E2 l0 c6 q! U
}MONKEY;' x2 ^; Q8 B7 I  Z6 y7 T' ]( K6 |
main()' o4 ?5 D1 G, d1 l
{ MONKEY *head=NULL,*p,*s;
; H7 p% m+ L* D: q  int i,sum=0,count=0;
0 Z2 Y6 p% k" T( ~8 z  clrscr();              //清屏) l; L- p1 T( V. B' M: r
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存7 I8 Z5 n% |# n& m8 q' [0 r  w
  p->number=1;p->flag=1;
& `5 ]8 r9 M0 |# y& ]6 D  p->next=head;; m4 K/ D9 M2 P, T  k) Q
  head=p;" U6 t3 L/ ?% u
  for(i=2;i<=M;i++)- v$ i) m# v+ w1 A+ w+ O
    { s=(MONKEY *)malloc(sizeof(MONKEY));& s- K5 X) J: Y' x
     s->number=i;s->flag=1;
# s" ]3 Z4 P, g. e* A0 X6 r( a     s->next=head;! M- X! w! P' D
     p->next=s;p=p->next;
8 Y4 j" l# P- E, k, d5 [- V( _' O    }8 z5 y' A! C6 d' K* Y% m$ F
    p=head;7 m, ?% E2 X  n2 Q9 j
   for(;;)
$ m6 s4 U! V6 L) n: h    {if(p->flag==1)' T* e# E8 F6 a( b! r+ B
       count++;
8 ?; ]% s7 s* t$ S9 R  M' w     if(count==N)- _$ g- d& l2 b0 d8 f7 o
        {p->flag=0;
1 |) s0 G+ c: x- A  ?         count=0;: e$ ?4 P! l, K; ?$ H$ e& U
         sum++;}
: G& H* {9 F. H2 y3 h: L     if(sum==M-1)* D0 o, y$ `4 o! ~3 f
        break;
( g0 C4 \; f* S4 r0 M& ~+ H; d" a     p=p->next;
6 e& m( N# r. K4 {    }4 R+ }) i& G+ T% q
    p=
- o& k* C0 h2 l, [! p    head;& X+ o) ~/ w' ]! {, ]
    for(i=1;i<=M;i++)
5 _4 A  D8 P! }! b2 C    { if(p->flag==1)
+ W6 z& s9 p: h* F        printf("\t%d",p->number);
" w& |' y- W/ F/ y5 h      p=p->next;
$ N9 ^0 y) Z+ T4 d; R" [    }4 Q  Q  Y2 x$ f$ F5 w  c
) J( r1 P. B8 T' |' k7 _9 h1 U

8 K5 k* N4 z5 l( F! x
3 S6 l, o+ r# q% J2 c: |. Y% U- u}

4 J6 I/ C& s; g$ K  s第二种方法:数组
2 s, r3 {& w  K% O" s/ X/ r#include<stdio.h>6 d$ L$ p5 G+ A/ W
#define M 8" ]( J' w7 K! K$ ]& Y
struct monkey
1 p. F  {7 S6 Y' A  K8 F{int number;, I0 n6 e# Q4 ^$ W! S
int nextp;
, T2 f& ^- c0 g}link[M+1];
( k4 W5 ~9 W- _7 m1 d1 n' O" s' A# G
void main()  Q1 n/ g1 U! d* X9 c" o, J; Y
{int i,count,h;+ ]6 x8 ?6 r8 U: }2 k  D
for(i=1;i<=M;i++). U. f3 R. {1 }
{  if(i==M)
3 ?: ~" w1 N9 r  _& \" ~   link[i].nextp=1;6 s" a5 }  `- w# j7 B
   else
1 C$ C2 ?  P7 Q7 {   link[i].nextp=i+1;
9 }* O7 s) N8 ^  x* v  link[i].number=i;0 e: j* S: Y/ H: y% b
}& W6 m) P# z0 R% ]
printf("\n");9 t3 k1 d$ G4 v  s$ i* V7 z, h. r' ?
count=0;# r5 K3 _% L8 `! `; A; G
h=M;
  G+ J( V- L3 J8 T( Q$ M' y9 R) ?printf("依次退出的猴子: \n");- G8 U8 u5 @: R& p4 W! L
while(count<M-1)
5 G8 ~! ~  p" K! B3 {{i=0;8 @; S& a: N6 H+ E. q
while(i!=3)
& c6 ]/ C7 T7 A/ z$ p; i9 I{ h=link[h].nextp;* `* Z) t( C, e3 j$ }( X( N
   if(link[h].number)
; m5 Z1 m5 C) x/ i0 V     i++;}: I0 l: J8 F# N( G: M& S4 Y
4 T  z. L9 R4 X+ m; d) S/ R
printf("%4d",link[h].number);6 Z; b9 b4 c5 l
link[h].number=0;
/ ^4 Y1 @. a0 acount++;
' ^# r$ o. d% y* v, c% q}
8 Q' m  ~6 U, Y6 b) v9 o% Q- R8 q. x/ z0 h- B5 {5 s* f, V
printf("\n大王是:");5 V' A2 n- O/ `$ r/ Z! l
  for(i=1;i<=M;i++)+ p" X+ `$ L; E" E$ F5 ~6 I
  if(link[i].number)0 g8 N4 t) m7 F; n; f) G* L! n
    printf("%3d\n",link[i].number);/ H) d! q( F4 }, x. u! f! I
3 Y1 i3 n) \$ G" I  g5 k' r

/ \% c: X1 g$ c5 v}

# j8 D# Y% }( C  d- z& B第三种是普通方法for循环
8 u3 G8 ?' N$ F/ X5 S0 _
#include<stdio.h>* ^9 e9 M) c* a3 k
void main()
7 t( ?% w5 F1 s! {# W) ~% V+ }{ int i,k,m,n,num[50],q,*p;
( ~/ A+ y1 a$ z- U    clrscr();- d/ \8 a2 Y9 j8 h  i5 n" ^3 T
   printf("input number of person: n=");2 b: k/ R8 ?! p# i: k. K
    scanf("%d",&n);" W& G8 v. X0 U4 F3 X; ^
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只4 q$ ~, Z1 s. n
    scanf("%d",&q);% F6 Q! p- W0 H6 P& [. {
   p=num;
. Y9 w2 z0 l7 R  for(i=0;i<n;i++)6 c+ j8 z% n4 f: H- j
    *(p+i)=i+1;, |5 h: k- |* G! j& T  e
   i=0;
& q1 J; c3 f  E- B   k=0;8 R- a4 X6 I2 W! p
   m=0;# a1 s/ G. v$ X; T7 o" j
  while(m<n-1)
* t* e) m% k3 c1 g: r  E   {if(*(p+i)!=0) k++;
- U! H0 ^7 U3 H     if(k==q)
% d# [7 }! K, d      { *(p+i)=0;( d  Y) N# C. B! w  t! T: D
        k=0;6 g2 t+ b. w% B9 W
        m++;
% T+ N5 Z( x0 j+ y$ ^* ?      }1 v( N- G* W. ]
    i++;8 O! ^- _0 q2 K: b) b5 s" S" n
    if(i==n)i=0;# ~) k2 D6 U! O$ n+ T8 P
   }
" G1 H  `) c* [! V4 U  while(*p==0)p++;
% d3 M7 R. Q5 `5 Y    printf("The last one is NO:%d\n",*p);! m: \! k' p, A/ ]+ M  g4 p
     getch();
2 @0 h" k3 i, i! d! s) G! o
0 h1 H) T: _' {$ @, s% f6 F}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
1 f; f4 f* Q. P3 h2 @$ tnamespace 又费马达又费电, {! x0 u8 G" c/ w4 N
{! T& e8 j- D/ S2 D7 F
    class Program
: }( N: g! Q: J. t    {
( F, L. ^1 m& D: ?9 Q  u* g" z7 {7 t        static void Main(string[] args)
! L% n5 Q- w1 X( ~  t4 u        {
6 U7 f3 d0 p  d' S            int m, n;
9 V: D  ^0 V5 A$ G: ~/ I            Console.WriteLine("请输入数组长度");# [9 ^2 r; Y9 L; _
            m = int.Parse(Console.ReadLine());//m为数组的大小3 l5 \/ C, _. L1 e: a
            Console.WriteLine("请输入要截取数字的大小");
5 T9 }8 U' O& T9 _  d            n = int.Parse(Console.ReadLine());& m& E/ L4 C3 H) }9 a5 D
            int [] numw=new int2 U8 \( L" A+ Q2 ]8 t
% v# v0 m' m4 k8 d7 O& Y- ~
&shy;&shy;&shy;;! g2 z* T4 t+ D6 B- P& h9 ]+ k7 r. T
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
6 l1 _3 `# p) U1 q& d: V& ?6 u% D9 r6 y            {
9 V$ V' e+ K0 m9 h( p                numw[j - 1] = j;* H2 J; W: z  O1 A- T; K$ I7 i7 @
            }
! S- ~( q' m: w            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
/ v! z& y+ a. g* `  x            while (d != m - 1)( o' E% p. W, }
            {% a0 N; f8 b  B/ W7 d' L. T
                if (i == m && d != m - 1)
' M. U+ x/ z8 @  f- L                {! k$ V# R* w! |' t5 P( _7 R
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
9 d- t0 Q$ g5 m" u                    continue;5 H- P' y, T! r1 F2 D
                }
/ q* H# r: H) _% i                else
, C' A' W( u; q* t                {
; S! q+ s9 z( {) b                    if (numw[i] != 0)3 z7 {& m: F/ N$ Y5 Q; T2 N  Y
                    {( U* i$ _7 D: H. Y: j" U- }
                        i++;6 _% i1 S. e  x! B- ^- q# C
                        k++;: P$ F9 p8 M- `& R* Q$ l; c
                        if (k == n)
3 |+ U  B  N) W' [* [                        {
. I% m* K! {5 ^                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# d, V4 c% `( L4 |$ p  r                            k = 0;; r0 ]1 F7 `6 s4 b! x
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1; c: a+ w8 p4 @: ?6 Z
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
# j# T5 J2 ^0 _& F. C# H: B+ V! U0 t                        }
7 `2 x6 y$ n- y  L, A8 U  j7 J" E                        else//输出暂时还没有改变数组元素的值
5 B) `/ F0 b6 o# r3 ?                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);; W# W9 a- p0 x3 b- x8 w1 S
                    }
" |' v9 w# G, y5 t                    else/ r+ c7 {3 x2 W5 r7 z
                        i++;//数组元素为0,直接跳过,不计数。。。! a( \  _6 _, W( R
                }
. G. a0 w+ O- @, N& A
1 @7 j5 [( r3 M: t* v: |$ u/ {0 ]4 M# R; c0 j& L1 p, Q4 n" ~
            }//结束while循环8 I* k/ ~) o  K. K& V; z
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; l7 Q/ u/ t# v4 ]6 E; M6 y7 \; H" a
           ' Y# C6 j3 N) T! ~/ u' H3 {( y5 u$ N
                if (numw[i] != 0)0 B" N( i. @; x/ u' t
                    Console.WriteLine(numw[i]);/ j3 b5 `- @2 j, b0 I' w: ~
           3 ^, |; M9 {. ~* Q
            Console.ReadLine();
; M3 f+ Z! j! `7 ~3 Q3 D  M; L        }5 u/ S( g  A/ u; m- y' S7 T0 R
    }
0 J2 h# N, A3 U& l. p}
/ Z% B: F: j7 |# }) y' n1 D. z7 H, 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, 2025-11-14 09:20

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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