鱼C论坛

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

猴子问题

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

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

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

x
大家好!
/ q5 N% _. f! \/ ?# d+ @' n! {这几天我在忙着编一个问题,我用了一种方法编出来!: Z  q3 l. @9 U4 n
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
6 h2 ^- A. A0 B注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 . }: U2 ]. O, h) C$ |
6 J; r0 h7 Z( W& c( E+ M
3 \+ H5 P& ^2 x5 ]
                            题目- K& u$ s: A: g: v
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。4 ^# K# |; Q# j+ e8 t
第一种方法:利用循环链表
! ~+ ]$ f3 }4 w9 Q" W1 X6 X) F#include<stdio.h>
2 t" D9 `" `) B#include<malloc.h>% k- q$ _. G" r8 J: E
#define M 8            //共有8只猴子! I9 i1 k0 g9 {0 S; F' D  e; Q2 s
#define N 3            //数到3只时退出第三只- L9 v( ]4 O$ z- n* R4 r( r, I
typedef struct monkey& E/ a9 [; `" ^
{int number;' k; r# L% I9 ~3 M& q: o
int flag;
0 S/ u6 [  c0 Q% ]: ustruct monkey* next;
3 x2 u% ^, `; ?0 b+ c}MONKEY;+ N: O, Z+ Y7 a( R7 s2 `  }
main()
" h  R; d: G; Q8 j/ P{ MONKEY *head=NULL,*p,*s;
3 m. |: E# S/ f/ C7 I$ m  int i,sum=0,count=0;
; ]- l; c9 @, F7 j  clrscr();              //清屏
  }. I% E+ N' z! q* k4 B  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存' x1 X. v; C; \) W
  p->number=1;p->flag=1;, `( R( E% C) e5 t8 a
  p->next=head;
: J7 [$ q2 G2 h- N4 H3 c  head=p;
7 ]) |, Z4 |, F* E" g! v  for(i=2;i<=M;i++); Y  `2 G2 A- T- t5 c* \6 |" Y$ h$ y
    { s=(MONKEY *)malloc(sizeof(MONKEY));
' Q5 D: C/ ^4 e* b$ Y. J     s->number=i;s->flag=1;0 C! X' A' W$ o" x& E  `8 i
     s->next=head;
6 t3 B8 B& g3 S     p->next=s;p=p->next;
, i. v% H, U  I  G4 `& O    }# V/ K0 e  T- `7 ?7 x! Y
    p=head;
5 K# v: ^8 R9 k" Z. ^# B   for(;;)5 u  l2 U8 N1 y+ N! ^& p
    {if(p->flag==1)4 y- X; n) p0 ]7 [
       count++;, w* ]" s" D/ R/ y/ P8 `
     if(count==N)
" P$ k/ `8 w% `9 [8 i  p        {p->flag=0;3 c- j2 O) H- S/ M7 W9 N; j
         count=0;' V; i( P3 T1 V; E8 K
         sum++;}
+ m0 H, \6 J8 H/ n, {     if(sum==M-1)
, Y) }1 v- F6 r+ O        break;
4 R* D# w7 |( x8 N     p=p->next;2 N! Y1 g7 H# H
    }
# t6 i3 G9 E" |7 w    p=$ z7 W  C5 P+ \& c* ^3 ^0 l. @
    head;
3 i- ~8 F  j% w  f. j+ h    for(i=1;i<=M;i++)
' D! _3 @( u2 ^    { if(p->flag==1)% W6 F# a3 u8 g# v  O, }) [/ T
        printf("\t%d",p->number);
: ^6 J& N! l8 E3 ]# R      p=p->next;
  z, B( X: A: E4 q  o0 P) |0 G  O    }
5 T/ k* M- g0 k& d
/ F$ t0 j/ {+ M7 c% B7 ^! X! ?7 p; g$ T0 U, k  X

0 t* |4 v0 L5 c7 z}
0 I8 d/ ~6 U8 a8 D6 H+ S  ?7 w
第二种方法:数组
! G: }: a% \  P: W#include<stdio.h>( d* M4 _; Q5 \/ d1 P- j* h
#define M 8: X5 c+ [' i$ ?+ o
struct monkey- e5 }! _9 g# ?. ]; @. M7 Q1 M/ C
{int number;8 y' v. S4 g, A4 @
int nextp;
, k' b4 [3 U3 q) e* F% R# {}link[M+1];: k4 w. s/ y. p" @

4 d2 w5 ]. C1 [! gvoid main()
9 S# B7 h3 Z' X/ c* i* i{int i,count,h;
5 E1 E5 v. A! q% X7 ~- \for(i=1;i<=M;i++)
& r  C% y( l& M{  if(i==M)! N; t  n4 q* t( \8 Q
   link[i].nextp=1;- r+ Q$ F- n0 O" G+ U( w9 ~8 A7 k
   else
0 h$ O. Q* T9 {# }   link[i].nextp=i+1;- K# @; Y5 s! A
  link[i].number=i;" U; H) w' u( {, a" {7 i: J9 K% ^$ l
}
$ K  U' R# _. E2 B! t3 z8 B5 Wprintf("\n");
. v& Z9 y% p) y! g; F6 hcount=0;- \6 e* {' |2 B2 T  x0 {" V, w; a% `
h=M;# K, L4 Z& }4 G, A# s
printf("依次退出的猴子: \n");  T6 G# Z' |* o. l+ q8 T
while(count<M-1)
2 O! Q9 X+ \: n! h{i=0;
- Q$ r7 h' K/ W. n, `' [! q! h( rwhile(i!=3)
4 N% N8 b* C4 U  h, I/ @' Q{ h=link[h].nextp;7 n; m/ {9 ~7 |0 X0 a. m8 Y
   if(link[h].number)3 h7 O% _; k' z) u
     i++;}% g# i$ Q: p+ ^$ N& H
3 i! X6 A6 |# e" c( [' \1 n& I
printf("%4d",link[h].number);0 ?/ K" c3 b+ ?
link[h].number=0;+ T9 y6 i1 ^# n6 _% e
count++;
& A0 s7 l" E( U- R}
. c3 Q" b& g" g  y; A1 |, X" W+ J. g
printf("\n大王是:");4 A6 p) t: f9 x' f# d( l/ e
  for(i=1;i<=M;i++)
& W' Z, _- }( b, f  if(link[i].number)
0 c4 r& }5 H! C6 W0 f    printf("%3d\n",link[i].number);
3 F' S- s1 e) e1 {/ n* R- G
4 `$ o0 }/ ~2 G4 T. T# `& e/ g  i! \3 O& _0 z% f2 J
}
% L3 A$ M* u5 j8 ~1 B
第三种是普通方法for循环

* M9 J5 V% c* D% ?#include<stdio.h>0 s& a  T1 l, T( ^8 F) M% D
void main()4 l1 A5 K' A$ F, I& b( [
{ int i,k,m,n,num[50],q,*p;" Y; |! P: }' n+ i6 w; S# y
    clrscr();% ?+ q0 _/ D+ |0 j& @* S. m+ j
   printf("input number of person: n=");/ j: `3 `; Z- w. F; O" }
    scanf("%d",&n);2 {8 K1 ~7 Z  t! D
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
8 F' |% n$ y: G" n9 H    scanf("%d",&q);5 {) y: v+ L* L; \/ u8 E
   p=num;
' ~0 x2 b+ j) [+ I" ~$ c9 U  for(i=0;i<n;i++)+ A' @4 r$ D* f7 }; D' f+ u
    *(p+i)=i+1;
, b( C% H) \$ ^. t4 ^   i=0;6 r' p( R/ w( B+ r
   k=0;
0 _+ O9 Q& c( @& R/ V) M/ G' h   m=0;4 ~4 S2 z3 Z  W4 P6 e) x
  while(m<n-1); p2 d) d* |& ^# G7 u
   {if(*(p+i)!=0) k++;8 |! h8 S" x/ L2 ]( j2 l
     if(k==q)5 w& H8 j* N" r. O- N
      { *(p+i)=0;
$ n1 g; a0 v7 b7 g2 n        k=0;! \; s2 X* @; }0 I' I, C
        m++;
8 h; R- \& [) o' I! q5 m7 i      }" ]3 ?  l% i5 v8 `# S! y( g
    i++;2 k) J" @2 o9 j& e' E9 G
    if(i==n)i=0;# [- K1 y2 C/ x4 k  W3 J# y
   }; l7 t  g* }1 D! c' K: ?. q) Y0 B
  while(*p==0)p++;2 |3 K/ m  P+ S$ P4 ?) ]
    printf("The last one is NO:%d\n",*p);: d" c/ a+ v9 ^& L% D
     getch();
7 }" ?6 h5 }9 Z3 z9 o0 V9 q! T4 ^7 J
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
1 S! Q5 A* @$ Bnamespace 又费马达又费电
3 T: l$ i4 `' B$ {  l+ O2 D{5 E( V0 Z2 d. u0 ?
    class Program
/ {. P' Z+ T$ X  p9 x' R% W1 }7 S/ o    {0 W% ^9 C5 w7 u
        static void Main(string[] args)
9 I- N# L7 i  e1 f        {
9 }' B# c( s7 X2 Y: _$ O- O# V            int m, n;
( v& [: ?. q( t3 S# m, H# W1 S            Console.WriteLine("请输入数组长度");
! c6 P! t2 v% a            m = int.Parse(Console.ReadLine());//m为数组的大小
* h  B2 A6 Z$ Y& o            Console.WriteLine("请输入要截取数字的大小");
, C  R$ a0 T0 W. O            n = int.Parse(Console.ReadLine());
- M/ s4 x9 {1 U            int [] numw=new int
, F, ?! W$ C7 n- R7 L
0 ~; b: w7 V# ^/ v+ W" n0 [; Y&shy;&shy;&shy;;
- ]5 A& G' K* ?3 F9 d% Q" [  n            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数; y) r, Z$ G9 ?( Q7 ~0 e
            {
. [$ ^0 _) U3 c# ?                numw[j - 1] = j;
/ O$ k. @# K+ {* V            }
* ~( H; Z: ~4 ]            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
0 C/ D/ k# G0 p: i            while (d != m - 1)
6 O- W4 o8 U7 x9 L. n! D, {            {" M( Z* ~! N2 Z7 G- u) y% k
                if (i == m && d != m - 1)! F7 n9 l2 O- @" `- B# U
                {- j/ I. Q" s' T
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
2 G, \  u; N2 s& o: ?( p5 g% A+ H4 q                    continue;3 H4 ]7 \0 l8 `
                }, C0 u' ]/ }! O
                else
9 ]" ~/ @$ C; R- ?- F                {
7 E+ M( j" b& U( H                    if (numw[i] != 0)9 I( F0 N: Q9 l8 y% C* S
                    {
9 M. `. m4 R/ d& P/ f                        i++;
/ s3 D  Y# w2 |6 v( M5 \$ a                        k++;+ r, w1 R4 I+ B6 Q
                        if (k == n)# q, g0 c+ B, u8 j' k# R
                        {
( }) F# C0 o! k) l( o                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
4 K! B2 M: m% x5 d/ l# {* ]) J$ n                            k = 0;4 T. p  Z* b" {' O  H+ T  D
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小15 c0 ~  x7 Z! K4 D+ H, H
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
3 n- x; G6 h+ S5 i. J. g                        }* s) y9 j7 Y& i7 m; C$ v- @, [* s
                        else//输出暂时还没有改变数组元素的值5 {* o% n, k: _. T1 f# l
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);8 k$ L3 o( i. ^2 e, O
                    }# S# ^; c; D" l6 o1 F
                    else; y2 ?* d, D5 ~1 G1 {0 i
                        i++;//数组元素为0,直接跳过,不计数。。。/ R* O! c: d( _
                }% o! F# v* C+ `7 z, Z
0 a1 d( z4 ~4 w$ e6 M
; P" Y( P/ ?8 m3 ~$ X& \  I1 o( f
            }//结束while循环
- H  \& z* ~" }; Y6 T" d9 ?            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
$ G. J6 w- r$ z9 b! u3 z           
$ [- `  L/ i) A                if (numw[i] != 0)
! W5 U' [2 A& M0 U+ \. x0 t                    Console.WriteLine(numw[i]);
, J' S  X* K! b9 c& ]) e0 V( D5 L% B           
4 W3 X+ U6 c7 w            Console.ReadLine();
, G7 M) N5 O4 _! w7 p        }
% y9 U5 P# Z/ c  {$ W    }
  W  ?" k" M: ~* K& o}0 a5 x9 X& c) O! z) W
小甲鱼最新课程 -> 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-2-11 15:40

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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