鱼C论坛

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

猴子问题

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

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

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

x
大家好!% z5 S  `) r( `
这几天我在忙着编一个问题,我用了一种方法编出来!+ j4 @! ~( x' J7 U
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
3 r/ c8 D$ J9 z: N注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 " u+ j  X4 Y7 A1 z5 }" |

2 o3 B8 W0 x5 ]. U
" a4 Y9 l" \2 N" k, O& e& x
                            题目
. r8 r5 _# I# d% `" j$ n山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。9 X* d' W" }6 z8 {. U
第一种方法:利用循环链表  o3 x4 Q1 \, S! r
#include<stdio.h>9 Z: i! n+ a, @/ n, j" A" X: h3 S
#include<malloc.h>, G, N$ R+ n5 d6 n$ w9 ~
#define M 8            //共有8只猴子0 A1 p; A( u- A0 D1 d5 ^8 R
#define N 3            //数到3只时退出第三只
/ J8 z# a! C- [8 A0 u( Ctypedef struct monkey  L8 j* e% a& N0 k& e$ j# F
{int number;: _  h  F8 Y- l% A
int flag;7 t6 ~: x" h' a0 {1 d
struct monkey* next;
* Q! N: Z! N, d9 w0 ^; s' p}MONKEY;7 f9 _0 z* T& ?6 |# d2 z& ^
main()! u" q( a6 M, G8 B9 V. c$ m* B6 C
{ MONKEY *head=NULL,*p,*s;
* _1 v8 S. ?- {8 N  int i,sum=0,count=0;
; ^7 D7 z1 B9 D, u5 U/ f" q) r* v# x0 z  clrscr();              //清屏
9 P% h6 b/ V  G7 N* T( w/ O  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
) T7 i/ ~- f6 u3 _( u8 v  p->number=1;p->flag=1;( g5 D# L% S; F. E) [, C8 b# v- K
  p->next=head;) L& u3 J1 k; N7 G1 U1 K
  head=p;
+ o0 ~# Y! e0 {! ~; W  for(i=2;i<=M;i++)
- q% t% U1 y' d) g2 m    { s=(MONKEY *)malloc(sizeof(MONKEY));
! d- y) F7 I1 ~9 r! ^' R6 x     s->number=i;s->flag=1;) `0 J: x1 f$ L$ v  y  f
     s->next=head;& ?) v9 r1 n" p, H3 ~7 r
     p->next=s;p=p->next;
2 Y) h' t( ?( l$ t    }# _) X) x9 ]8 E3 _; B
    p=head;2 v6 i! e5 z% R% z2 M% y, n2 l
   for(;;), j* `( i' U: C% U+ h' f2 r- U9 J" C
    {if(p->flag==1)5 u, B& g: c5 I9 ]' k
       count++;
3 y! h* e, I% e* `     if(count==N)
* K  `9 N) i. j; O        {p->flag=0;
( a8 E2 Q' K! T+ `0 P3 w         count=0;0 H6 P" m" H, N
         sum++;}
6 h0 n* _9 _" q7 q3 ?3 a% a) p     if(sum==M-1)
* S( H, X8 [1 g! z        break;+ }& r! ]/ \4 |( D
     p=p->next;
7 |8 I7 ~4 i' S    }( D- c1 z; n& Y" h" g
    p=8 z/ Q2 ^/ g3 _: P- M! a
    head;4 i2 Q$ A( w* N5 e0 ~7 L2 a
    for(i=1;i<=M;i++)6 q3 l+ c" A8 Y/ n
    { if(p->flag==1)0 c4 n: R" ?& \. \+ N
        printf("\t%d",p->number);& N0 j# |: G& z+ J
      p=p->next;4 }" f; Y2 i9 p
    }
4 n  o! o% k& s2 l# ]* U7 E: ?3 n' w# y% b: U( r
  Y& t: X6 P! n. ]

' v! F( E( B, D) m+ P& `% j}

" R7 G" g5 m7 Z% Z) V第二种方法:数组2 _9 C1 n3 z& p" a1 D
#include<stdio.h>
: P4 K9 ^* H; [3 u* U#define M 8
: w& s6 N( h$ ?struct monkey
; ~, ~8 j- ~; m$ L{int number;& I, t# j% F- K  Q- X# D, [
int nextp;
; H$ z/ U' ]) J}link[M+1];
/ o. |4 D+ R' a6 i8 c4 y
6 y; w) ~0 g( ~3 F! j% kvoid main()
/ \( @) W! g$ y: i; C- A. k' x9 R{int i,count,h;4 D5 M  W# E! m, k' r! r' \
for(i=1;i<=M;i++)
! F& m# R1 A5 G6 W{  if(i==M)
, R* J" k) n7 J   link[i].nextp=1;. b( ^5 z0 ^7 {
   else; l5 f" F% C2 A, F/ W) T; z* D
   link[i].nextp=i+1;
) x( u( W/ a- B: V/ G  link[i].number=i;9 A+ i2 G% S8 Y9 h9 H+ l* A
}
2 f" \3 j9 \" w2 d* \+ @: O0 A! Vprintf("\n");
. U: }! ?0 k" v) gcount=0;2 [7 k+ l5 \  w9 U( b- ?7 A
h=M;0 E( i# A$ f" p. {: |7 ~1 \% E
printf("依次退出的猴子: \n");$ n* R3 i+ n. G1 X1 D( A
while(count<M-1)
; T: d# I2 O2 v7 Q{i=0;
3 c; S/ c6 g+ w4 q* Ewhile(i!=3)
4 O* L: p" v& x0 {{ h=link[h].nextp;
( M7 A% I0 K2 l5 F9 Z/ |# ~" N   if(link[h].number)- n, T. G( g$ X7 h0 g& B6 `* n
     i++;}- G! I0 k5 A/ H+ {* ~( W9 a
. c3 s; \1 a6 Z0 {* V9 q' x& p; v
printf("%4d",link[h].number);. r) |; W+ t9 N/ s9 `
link[h].number=0;4 T( L3 c) l/ G/ l
count++;) ?3 a6 q  L4 }+ i% H$ `& H
}2 |" _" p+ y! r1 ]
2 W% W5 s( j* m# m
printf("\n大王是:");
# _+ ?) q8 }! @  `# T1 u! N  for(i=1;i<=M;i++)" p& b; v5 r. _5 ^8 f$ y
  if(link[i].number)1 u) q" z4 `; r4 H  ^0 z$ R, z1 T% q
    printf("%3d\n",link[i].number);
8 `% N) n% B& ?7 ?6 I
5 H3 I6 ?9 E/ N
1 ~/ e# K2 v+ S}

" d0 X' q% h" i" C8 A( p: [8 s第三种是普通方法for循环

7 `3 q: F/ B; d# j#include<stdio.h>
( u  Y1 ]7 L, D6 }void main()1 ]/ d5 y; }! S7 Y) @2 S, [
{ int i,k,m,n,num[50],q,*p;! k0 x) Z  J0 A" ]/ E
    clrscr();) W: G9 c2 `( d0 F5 G+ L5 W
   printf("input number of person: n=");
; S+ [; S, y  ^( g    scanf("%d",&n);( f$ s8 C' Z# W9 i
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
0 z( g2 g8 [3 A    scanf("%d",&q);
- S! o% [5 h) V/ I% c$ p   p=num;
" v+ F% L; O( g0 s  for(i=0;i<n;i++): Y; z, h* m( I0 l8 w6 l
    *(p+i)=i+1;9 V0 e! O. X  E: u0 p6 x! _
   i=0;; K0 ?) `9 K& U) `, i; k( W* A! e
   k=0;  o$ }/ [2 J1 T' ?; y
   m=0;# c, j- r) y% Y  n
  while(m<n-1)
0 O8 ^) o5 o. U( i# z6 q   {if(*(p+i)!=0) k++;8 i$ V0 o: k7 Y0 i+ e3 a
     if(k==q)& K4 S1 }8 I) Y1 U+ \( p$ _% l
      { *(p+i)=0;. t9 X7 [3 G1 m! ]) O
        k=0;
4 A+ M6 M# Z+ w3 [        m++;
0 H! a2 ]9 h1 U% A5 m      }1 @% K5 C% D$ O
    i++;/ B  R, d$ p/ w5 x  U8 C
    if(i==n)i=0;- I3 F- J* V3 B* F; U! K3 x8 V
   }/ V- E& f* A( F" o* E
  while(*p==0)p++;8 g' a6 z3 J3 B) z
    printf("The last one is NO:%d\n",*p);6 S5 M/ _# d3 F" X- K5 b% q% y
     getch();
" Z7 j5 K7 r, D: f, A! P' C4 Y+ C3 i& t4 g8 n
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;+ r, ?3 o  U- Y. j' g2 G" |
namespace 又费马达又费电
; B0 a6 z5 K& }/ v{
4 z7 o7 ], p) D. B/ m; Y8 _    class Program
5 u' F5 M% b3 H* i4 P    {
/ F( r, b0 z5 ^6 Z. X  \7 W; R        static void Main(string[] args); x- P& s0 s( m) e! x* u
        {/ d, y* d0 L7 {! o* A7 d' W2 H8 ~
            int m, n;
9 l2 d5 u+ `; J3 E* o            Console.WriteLine("请输入数组长度");% Z. I/ Y( @6 O8 f) K
            m = int.Parse(Console.ReadLine());//m为数组的大小
5 ~8 o2 U( x! K' s            Console.WriteLine("请输入要截取数字的大小");# q( d2 i8 \9 ?: u( ^' L. r
            n = int.Parse(Console.ReadLine());8 Y  K; z5 ^& ~' v4 O. I" x
            int [] numw=new int' l4 ]2 q+ f7 q- ~1 S6 q' d

# v( y0 v" }: }2 J5 ^: N&shy;&shy;&shy;;
# [$ q- f, u# d            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数# ^& K# z" Z* T6 e! U7 q- Q) C
            {
4 J& b2 c  x8 a8 s( n9 V                numw[j - 1] = j;7 A) o- v+ D- d9 h7 Y0 A
            }
; J4 U/ |2 ^- Y( u; w9 Z            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!- ?' b# W" g: l- R' p
            while (d != m - 1): y( ?8 C! @' W' z# J0 G0 w
            {
; m- q) L2 X; b9 H; _4 s                if (i == m && d != m - 1)# ~* t$ @8 c% a. I; K3 I
                {
+ ^% S3 s- I+ b6 ~+ C$ G                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
) e" J1 n- d, U- v1 {5 g2 S  P                    continue;
9 Z! H: N& c" }# K: [5 K# R7 P                }
  c' H  u1 Z6 o                else0 A0 o  K+ o; y+ H6 z
                {2 T5 H; y$ v  j' T6 \& g5 n. F
                    if (numw[i] != 0)  M9 Q0 j/ S' V
                    {
) J1 I; s2 ]& M  T/ Q* m                        i++;+ y# x7 f' j4 ^- |  j
                        k++;: i: j1 j% o: z, o0 `- D: G
                        if (k == n)9 a1 a: r# f6 d
                        {: n/ y2 O8 F* @1 L6 Z- w- L
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# u- R" x" o2 k/ m, u# Q+ `5 |                            k = 0;
( R# X: j0 e  }! j, p+ r              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
. H, l. k9 n7 ]                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
% D; A1 a# P) j" Y" I0 Y( s                        }8 o' [( k. I* y
                        else//输出暂时还没有改变数组元素的值
' h; p0 h) F- S9 d5 P                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);# e6 h4 w; I9 h' w5 s1 q0 V" a& x
                    }
! P9 i8 h. j. Q* v: ]9 \3 P9 ~                    else
( i6 @* @3 a  U2 {2 _5 X                        i++;//数组元素为0,直接跳过,不计数。。。
) W; C4 o1 r! a4 i8 }1 A                }
$ c1 w. U1 p# g, r3 d! f 4 x4 d. r+ Q% j1 A

: s& V7 V5 W5 G; ~# X# ^            }//结束while循环, @: i  O# V, r. k
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
. o3 I( O' |3 D' X5 ~; F           
0 Q% n. u% t" N                if (numw[i] != 0)
$ R( s% t# M3 e# r                    Console.WriteLine(numw[i]);
$ X3 M  |: G( c           
8 e1 p6 F, K3 u* ?7 I            Console.ReadLine();4 x$ Q5 o5 F  Z' E7 [. t2 L( D* D5 R1 @
        }
0 |, I6 [6 g8 H8 _3 e7 O    }
. l5 J/ s& n! \, [! P}
, b  b1 d2 o3 V, g1 d- g# U  f+ J+ x
小甲鱼最新课程 -> 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-3-17 03:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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