鱼C论坛

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

猴子问题

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

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

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

x
大家好!
& I+ n- a$ E) Q( w4 n7 y0 [5 {这几天我在忙着编一个问题,我用了一种方法编出来!8 d/ I& X, D; ~6 s5 o! r" C3 V
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!$ c" @( ^3 l9 ^9 Q" G7 ~
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 9 m1 R1 j5 ]" ~2 Q6 g! E0 h
1 x5 D: v$ F* @. c& V7 c9 b

' N2 J. y) I* r7 L- A! c" E' q
                            题目. w4 ]! r/ G# i' ^
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
3 K! K& u( T; q+ l: W- [8 W" C第一种方法:利用循环链表. M0 w$ ?  k% C' R
#include<stdio.h>0 E  |( `1 d% v% `; u9 O
#include<malloc.h>8 R% w" c% A9 w, r2 k) g( D
#define M 8            //共有8只猴子0 Z( T$ I" x9 z! D) @
#define N 3            //数到3只时退出第三只+ _. g  E5 q' z# N; u, w
typedef struct monkey
$ f9 [% _3 i# F. [$ e" |. x{int number;
% ]8 T2 f$ s& {2 G) x8 Wint flag;: \: `& Z9 z: V2 ?" g
struct monkey* next;+ t  k5 I# V" t1 @) r
}MONKEY;
- R) {. B# @) s, |# D% ~! Mmain()
. Z- p( S; {1 U/ v% F: L( m& M{ MONKEY *head=NULL,*p,*s;5 P1 D, ^% ~0 \; ]
  int i,sum=0,count=0;2 b1 r  Y, f: J0 f" i; O
  clrscr();              //清屏: l7 e1 g- O: p" s) {' S( ?
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
. Y8 f) z6 E) r, \. c4 |) f$ o  p->number=1;p->flag=1;
4 C8 J/ T  s* |+ ~. P3 s  p->next=head;& W' S% {" i( \% Z! S( r5 D: \
  head=p;! I$ W' n3 r5 A( m8 L
  for(i=2;i<=M;i++): u* d1 q% n) @( |
    { s=(MONKEY *)malloc(sizeof(MONKEY));0 Z: E/ @  |" t- P! S. q
     s->number=i;s->flag=1;$ b+ g- N* I4 P( D: d' D
     s->next=head;
( R7 u: v( n. ^& {% G7 V     p->next=s;p=p->next;
+ M" J! f: B* k! Y- Q    }2 q0 ?/ m: D/ d$ o# F
    p=head;
: B. T: w5 ]5 T5 L8 S9 @' C   for(;;)
- _8 p; b' ~5 V    {if(p->flag==1)' I4 A8 v' j5 e! M
       count++;* v; \$ _% S7 t" Y8 [% _
     if(count==N)
6 ?/ T2 h- I- R        {p->flag=0;1 N# u; U& C! H, p
         count=0;, A+ `& U/ A+ Q+ o4 j: ?( v( U0 G) P/ c
         sum++;}) l+ ~+ @+ d* B2 n2 c7 X) w5 w
     if(sum==M-1)
: Y5 K3 U- R6 m; v, N        break;* P8 m! E& b/ Y5 v) ~4 ]; i
     p=p->next;
/ z) D  l1 d8 t; r5 J: b5 h    }% s, d; x- ?4 D, n9 c: r+ C  m
    p=6 B/ s, h( i  a7 x
    head;
1 A) s+ r+ _4 Y! b$ k" [3 Z    for(i=1;i<=M;i++)& B7 M5 Q  T0 y& s3 d& i
    { if(p->flag==1)
1 c+ z9 u- T' U3 B8 s        printf("\t%d",p->number);
; E" e; z6 r! G" h1 ~& v7 a      p=p->next;* t, h# r: B; A) v
    }* J, A- ?+ H( j; |# P

3 t; f2 a  s4 u' m7 K/ e" U9 x
, }) X; N$ l; l! S, @2 L
2 v8 S( e3 g; v2 ?& A* g. l1 Q}

) `- a5 V: E; f- J& J第二种方法:数组' Q. W" @0 M' S% n" P5 m& e  U
#include<stdio.h>
4 _/ R% ]4 f6 S7 H#define M 8$ J5 E4 z8 [7 D
struct monkey
& d& n' X; p& A8 X{int number;$ |- S9 |  J* q$ [
int nextp;1 |3 Z, N/ H# v8 [' r% p
}link[M+1];
( {* }$ G0 n; r) U, @  z, r2 P2 g1 r+ k- B/ ^: `
void main(). O1 {9 {. E) q9 I1 F
{int i,count,h;2 @, u+ H( a9 Y
for(i=1;i<=M;i++)
  D* e2 Z3 j5 j9 {8 h0 f- W{  if(i==M)- T4 L* k/ B8 o. m, T1 ?
   link[i].nextp=1;
& i9 m8 }3 Y9 e) B, g   else  V# w9 \( L4 }  l
   link[i].nextp=i+1;8 {- C  ^3 @' W+ O4 @6 R. F
  link[i].number=i;- M' |! W4 p4 {* P6 q
}8 ?: d8 b! }3 b3 @/ u
printf("\n");
6 X5 Y- @( C( {- o$ f- B( J, m- Vcount=0;
/ I7 u" X( y  dh=M;; R* C5 h. b, _
printf("依次退出的猴子: \n");& f$ M$ P4 Z' u6 g
while(count<M-1), Y) M0 n5 p+ O# w. U- p
{i=0;* A' D& U: w# e
while(i!=3)
& J. D; X# R3 ^% n9 }{ h=link[h].nextp;
. l9 F9 s; ^1 f/ r$ t7 A) A* N   if(link[h].number)0 v" {  I& P8 B5 n/ w! s* o1 E) n2 x' p
     i++;}/ n# \# E  t4 }1 X1 l- Q3 ]. v

$ _, a# D, \4 J* ?5 {4 Zprintf("%4d",link[h].number);- J" w( w( c" x" s1 r) P4 M! ^
link[h].number=0;
  E7 S7 y0 J4 V! Rcount++;
2 L2 M, d0 ~! @! C1 _}
6 T# I/ r2 T0 m, }+ V: H
2 L1 D$ ]" R' K9 Y  x' B- L  Aprintf("\n大王是:");
- Z" M6 ?* u7 t& y  for(i=1;i<=M;i++)
7 ~1 V) l/ ~+ a# K) q6 {  if(link[i].number)
; E  F+ c2 ]0 _5 {    printf("%3d\n",link[i].number);
7 b  G1 S3 q0 ~( N. y
" C+ I/ |& I4 Y$ ]
$ i5 I& }* z( ^5 |' U: \}
% E9 i1 Z4 g4 M7 o/ e  R' [5 E9 w
第三种是普通方法for循环
( X% p) o- ]; L: \; M8 A+ |5 |
#include<stdio.h>" k4 I0 E- q; D. f& s; m/ C8 r
void main()! y8 O$ \0 w/ A1 }; [0 L
{ int i,k,m,n,num[50],q,*p;4 ^* Q  w) K/ K
    clrscr();$ K3 u* x5 _, @- I
   printf("input number of person: n=");' m, q0 I6 ?# t" ^  h  k7 V
    scanf("%d",&n);
! ]" r- e' @! D, A7 [' k9 |; gprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
& S) c: X2 k1 C    scanf("%d",&q);, ~7 |4 M' E0 R! u9 H
   p=num;2 [2 C4 [. B) o
  for(i=0;i<n;i++)
, h/ L4 O+ p  s0 u    *(p+i)=i+1;% s7 L% G6 l) r. E9 ~" n) l5 A- @+ }! t
   i=0;5 W3 \+ }+ G& P4 g6 R5 s9 T
   k=0;
0 w: Z1 L2 Q  }. Z$ z; v4 t2 H9 {   m=0;
' g. L3 K( Q# v( @  while(m<n-1)
5 z. I* [( J' S% H6 @1 `# P% j   {if(*(p+i)!=0) k++;
3 `6 l8 c) |4 P- G- f( S) X     if(k==q)
) O1 q5 q3 \( `  o7 \6 O2 |/ r      { *(p+i)=0;
4 g% l# \9 b9 Y7 `2 u        k=0;
- e) z9 \1 ?7 K$ V0 Z/ Q        m++;' W1 u2 Z$ n  v
      }
' r0 J) ^9 p$ N- n; U    i++;/ Q% s% \! {8 p/ B: [0 `: x
    if(i==n)i=0;- G/ f, o: @) {4 a* d4 B% z
   }! O! Z+ k, Q5 v! O& T
  while(*p==0)p++;
4 ]3 t! P8 }) h& x    printf("The last one is NO:%d\n",*p);/ j: |, U# F0 {! c, j" [; D; _1 {
     getch();( s6 K! `. A9 r* Z! \( v( I  r

7 p5 H& E/ _* V- u" i}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;& j; ?& U3 T( e
namespace 又费马达又费电
3 W# R, T1 w; M' ~9 K% `2 u- z: A; [{. S: G) H- F- m( {  F3 ?: k
    class Program/ r( \. d2 v- X1 E/ f6 Y
    {
4 v3 g9 q6 r( n        static void Main(string[] args)
6 s# P- I. ?; D/ C( V  p        {
+ }  O* D- Y! m2 s" g8 ?            int m, n;7 Q% r) l4 S% q* e
            Console.WriteLine("请输入数组长度");
; V8 w& b( J8 s$ Q            m = int.Parse(Console.ReadLine());//m为数组的大小
& \4 ^. j+ h) |7 o3 t7 T. m' |            Console.WriteLine("请输入要截取数字的大小");
$ q# _6 m$ G' w; U; w* ?/ e: `            n = int.Parse(Console.ReadLine());
3 O+ X0 B0 ]( B' N+ g( k/ T% X            int [] numw=new int0 y  N8 ]: ?& O" g! s

9 Q4 B% ?* B( e; G5 w* p6 N0 N0 z" ?* ?&shy;&shy;&shy;;' [) s! V1 }, f
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 i$ N& W5 r' p8 a
            {4 Y/ D1 F( y7 w8 Q- \& m% T* @+ U
                numw[j - 1] = j;
3 T/ t/ V7 N7 W! D# n            }& B# R" \; U) p& S( o% E
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! K! {" g9 i* |$ A7 B6 F
            while (d != m - 1)
3 a4 J6 j* S0 e1 Y- i/ P/ Z: Q            {  _  l8 Z  t: t, t, P" L2 w
                if (i == m && d != m - 1)
; s" h( s. B' P% _' ~# D                {& g- Q, i8 b7 e2 k
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!9 w6 X% B' W; i! ~: c7 X
                    continue;
; A$ T7 W( w4 L3 k! C( }                }
& \1 L3 s: W6 s/ D1 `+ v/ A' \                else* u+ F# C  N7 G0 K: c
                {7 d- z* s+ V+ K/ e
                    if (numw[i] != 0)
( |( h; ]0 r" R. y. v                    {
2 c- ~2 ^0 q$ f& p& X9 j/ a                        i++;
* I( {( I5 ]9 \                        k++;
6 x1 T$ y. u: p3 G                        if (k == n)
$ P; n2 {. y# O0 F$ P9 d                        {
* M. o: V  u2 f( H9 H  ]1 P                            numw[i - 1] = 0;//把在n位置数组元素的值改变了. s% ?) g/ y1 x+ L: k3 [9 z* q" r9 B+ h$ f
                            k = 0;/ i( y2 b- V  ?. J
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小15 y4 I+ m8 R3 J
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: @: L, q# \4 u- H+ P) Y( M
                        }
  i& Y& _" @6 s% L3 @                        else//输出暂时还没有改变数组元素的值
+ |7 @& [3 B4 ^7 ?  D1 }                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);* B1 I7 }: ~; [1 R
                    }4 [5 k4 b2 f+ f# o
                    else
! {) K5 J  [1 U/ x) I. b( V                        i++;//数组元素为0,直接跳过,不计数。。。  `5 Q. {# Q2 ?6 ^8 \& o
                }. D$ c9 `8 r/ P. G2 K
3 a$ v& f9 A( P# w4 K$ u
, w2 L" {5 x* b* H+ f
            }//结束while循环
& U! O' T0 g' g5 q6 q            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
/ f' f2 R% Q3 c1 s0 e+ O           ! c6 b1 k$ J8 Y
                if (numw[i] != 0)
8 b4 m: s7 w% [7 X: I5 n                    Console.WriteLine(numw[i]);
( A) v4 A% Z: x/ L) V  D  Z, n; f           
5 j$ D' F1 q  w# k            Console.ReadLine();
( L8 S. Z5 i& J3 A6 L; P/ A        }
$ r! l2 @6 h, K1 E2 n* C- F    }
3 {: S& r9 s9 F: O}# Y# E% J# w5 F) [/ 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, 2025-10-15 21:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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