鱼C论坛

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

猴子问题

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

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

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

x
大家好!1 y/ n% D) O3 W$ j
这几天我在忙着编一个问题,我用了一种方法编出来!5 d' ~$ \# f- H, w
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
! a9 K4 Z' N: v! {6 o! X7 H注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 # o8 T; |, ?( v# O2 f% r( J6 q
7 i* V7 i$ L! `6 ?
* S- \% K& U. e
                            题目& K, _/ V+ j$ a3 ^% k% {* }. K
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。% ~3 x6 u, [/ i- K8 B  N  F
第一种方法:利用循环链表5 |0 \8 i- l- Y
#include<stdio.h>
  |1 z: y7 H* V) u5 |: @7 c#include<malloc.h>
3 v* x0 o) k' D0 y8 E#define M 8            //共有8只猴子
) @1 k5 O7 s) B- P' e5 b3 e#define N 3            //数到3只时退出第三只
$ h' j5 r  w0 E3 n# Wtypedef struct monkey
# R5 w' |$ y1 v  P{int number;
3 Q& u( w- l& y$ q: Sint flag;
( G8 e7 |. F4 c4 Mstruct monkey* next;, U& J' M% f0 E: m! [! `
}MONKEY;
- ]7 J  D2 K$ N$ M4 amain()1 _0 K  f* o/ U0 t
{ MONKEY *head=NULL,*p,*s;/ P% k% n+ [; u! M5 M* m7 U
  int i,sum=0,count=0;
4 e. b' o! g, j& I: j; ^  clrscr();              //清屏3 F1 p: K2 f3 f& g5 F" C/ I
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存6 T  P% p$ `* f! z% d5 a3 l3 j
  p->number=1;p->flag=1;: K3 G8 i% K) P+ J
  p->next=head;8 L, A1 Y. h, p  l8 ]% {2 x
  head=p;2 X* E1 s# W  Z$ ~; }& O. d
  for(i=2;i<=M;i++). b8 \: w; U, N
    { s=(MONKEY *)malloc(sizeof(MONKEY));1 o8 [  ^1 o# N
     s->number=i;s->flag=1;: h# g( \1 {# }' O4 Q! s
     s->next=head;
( \1 g; M% [2 G& N     p->next=s;p=p->next;- e: I0 j$ g0 N1 o+ ]' t
    }9 D' f2 H$ i% |$ h
    p=head;% o) }0 \, m9 O1 d5 K8 x* w5 H
   for(;;)
. i1 d+ U" Y& S$ I- W+ V9 I9 e9 j    {if(p->flag==1)! [8 w( M9 _3 G# z
       count++;1 P5 ~* c9 B8 e1 q7 b. O
     if(count==N)) O0 q0 T/ V. [: v6 B1 [
        {p->flag=0;+ e& S: O# E* d8 F+ y1 X1 L
         count=0;$ {' M9 y0 l* g4 E- H+ p
         sum++;}
1 P. t0 i0 {  ^     if(sum==M-1)" @2 S( n# {& k6 ?1 \
        break;- t( _  p4 r9 l  i1 F
     p=p->next;
' e- s# C" L2 e% I3 Z5 g/ D- C6 B    }. M5 d; b) t! H4 v& ^
    p=
; Z8 X# k$ x) N& p; s& Z    head;
$ N0 }3 @: Z% a0 a1 e" `. D$ r6 H- @    for(i=1;i<=M;i++)
* c7 I" L! `9 ^( K    { if(p->flag==1)( V$ i+ O( I) f$ i9 D' ^
        printf("\t%d",p->number);
$ u2 r1 R$ l6 y$ n# I- U7 l3 k! ^% n      p=p->next;
3 M+ l2 h5 |& G/ v0 D: A# N" m    }
: l$ W" ?& `# D$ v0 h! L) n8 o5 z  C' m2 W

( y9 `# [5 s4 X- \4 J( l, d
% @7 v- n4 T7 @( W}

% ~' e: y% g9 i( o0 C第二种方法:数组1 D7 V3 x6 _% O4 I1 }( m' R" a
#include<stdio.h>, ^, D+ @! F9 [7 Z2 ?- N/ L
#define M 8
' n' C4 d' O9 E0 x8 r( estruct monkey
: z$ i' \, J9 B4 O5 Q+ {{int number;8 L3 t1 e& a9 i8 [. D
int nextp;  K% w8 H1 E8 Y5 P; F
}link[M+1];  c' E  V6 _9 y# m& N

; f" Q8 T4 N( q6 k  q5 Hvoid main()
+ ]1 H* q4 s' J5 [{int i,count,h;
0 O0 r1 l! P$ ifor(i=1;i<=M;i++)
0 n: }1 X" n4 U5 Q2 w0 u6 ^{  if(i==M)
$ Y' @" W. T" K) n   link[i].nextp=1;, ]; N2 W, c3 H* ^
   else
& b8 N4 n/ \. s3 X" ]1 B. e+ ]   link[i].nextp=i+1;" E4 y  e" i4 N2 P: G7 W6 t
  link[i].number=i;
. F- u* q8 }8 W; u) d}; _" L9 Z. ?" H1 \
printf("\n");- w; {* ^# G, G; _
count=0;
9 k: A8 R3 Y+ N0 H6 `* a& _+ Mh=M;- b7 C, Q  v; X  D8 A# a
printf("依次退出的猴子: \n");
) p+ k5 A5 b! Y# Q- T7 K( u& zwhile(count<M-1)! @6 U2 t1 M4 x! p3 i2 f9 _5 q
{i=0;, u: B# e& k' e9 e  h
while(i!=3)8 Y) n$ \: g7 O: W
{ h=link[h].nextp;8 C1 R: j# ?6 D  L
   if(link[h].number)$ J  w6 s  c0 l+ x$ ~- _
     i++;}
7 p* z3 D1 A; d3 p' e7 A7 ^; F. E! N: R4 f& D
printf("%4d",link[h].number);
& m5 B+ R" L5 {4 M4 @link[h].number=0;
' ]( h6 r3 \6 O" b; X- Lcount++;+ ~) p! w# u% b2 [
}
5 q& {) j& h$ h1 W" e3 L
: f" E/ M4 _( x/ Q- K; v6 Bprintf("\n大王是:");
8 |6 Z' [# a1 R0 r  for(i=1;i<=M;i++)5 R1 m; u$ C6 s8 x
  if(link[i].number)
! [  y6 h: s8 O6 G+ ?4 u9 I    printf("%3d\n",link[i].number);
5 ?  H+ z) ?: P1 N' G) [
: |" J5 ?# }8 k! W8 e3 {9 N! G# g" }9 }+ m/ o! j. r" d
}
% X# Y) b' C# y! P3 _
第三种是普通方法for循环

' l' @. I  K$ E2 O#include<stdio.h>: ~) j) O' V/ G# Z
void main()
6 _+ U, H( u2 c; ~$ c{ int i,k,m,n,num[50],q,*p;4 X' N8 f5 ?& E$ y/ ?
    clrscr();" M5 J1 {5 V; n: L' t
   printf("input number of person: n=");  K9 R0 V7 T$ C" |$ q* ^
    scanf("%d",&n);: g# D: V/ u# L; W8 t6 v
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
3 R9 X: {! Q! m/ W# R* n    scanf("%d",&q);& t9 K- x3 ]5 o
   p=num;
: r7 A6 \, l( Z) O) P# a( }7 P" m  for(i=0;i<n;i++)7 g( w) Z9 ~' c8 k
    *(p+i)=i+1;
3 f5 b5 K+ f  ^, t. ]  Z   i=0;
6 a- ~/ l; A( R0 u" O   k=0;
2 i, w2 S0 [5 M; G6 C1 F   m=0;) q9 b( c& R6 N9 v8 |& h: U
  while(m<n-1)& ~. Y: N- ]% w9 q# B4 a
   {if(*(p+i)!=0) k++;
# W; b) e( B1 S. e     if(k==q)  x' y9 l/ }/ g/ O1 X8 B' P
      { *(p+i)=0;0 u3 e# h& A: t; C3 L' h8 C+ U1 Z/ M
        k=0;! x8 l8 k3 B* s5 ^; I+ o9 W8 f
        m++;3 R0 _5 C' x8 d
      }
5 `! i( i9 _6 w: l1 f" E: X    i++;
* t' y) a+ j  b* e. q3 r) @3 {    if(i==n)i=0;
- u2 u/ H8 h6 B- ~8 H- r   }. t% h  K# I) a* ~' s
  while(*p==0)p++;
7 T6 A  K% [$ l6 B/ p% O  V1 H# A    printf("The last one is NO:%d\n",*p);  H1 |. S9 C( Y; o; U
     getch();4 n* g! M* I9 s
' ]$ K5 N* [$ A; |/ w5 n7 P
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;4 J, |' e+ |3 L4 X/ P! H7 R
namespace 又费马达又费电
) z- b' Q) H6 E0 p# O) A8 x( R{
. p6 l& l; ?  W4 M    class Program
4 c' A7 O- o  P' ]; G2 N    {
7 ~/ c( i! }* x- Q1 H8 [        static void Main(string[] args)' |3 C& p' ^2 i1 o( U
        {. d: f) i* V! C) x; p# r, g3 K
            int m, n;& \" F) k5 c0 C& r' V
            Console.WriteLine("请输入数组长度");
7 c0 h7 m6 Z4 g( k# @; U            m = int.Parse(Console.ReadLine());//m为数组的大小2 }! H, K1 @- a( S4 E8 l
            Console.WriteLine("请输入要截取数字的大小");/ I: I  `( ^" r
            n = int.Parse(Console.ReadLine());$ n& E* C: d5 ]3 H6 ~3 ]
            int [] numw=new int! L# L5 b! @& H- g/ ]1 F) Q* W7 t# K
: _/ F0 E3 C- `$ W  h% f6 C4 B
&shy;&shy;&shy;;8 \# H  N2 R( K1 j9 V+ d1 v
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
$ K, {  l" o/ |  J            {4 P) u0 m' E. e7 L& _% Y
                numw[j - 1] = j;( [8 c8 z- s: a7 n1 ~: v; {. Q
            }4 `1 {/ A- z9 U
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!3 c# g$ E& C: ~- |# q1 J
            while (d != m - 1)1 Y! W; }" [* W( Q0 y
            {+ O$ ^6 v2 G& L; T# V6 u) d
                if (i == m && d != m - 1)$ W7 m* x0 O0 {) `& W6 B$ t
                {
; G6 }3 H. [3 f: F: h                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
, k: e( L0 ^; n                    continue;
2 b5 J$ H3 ]1 Z: t                }1 ?0 N& m' \" d- ~5 Z
                else
' c2 r6 u# @4 @2 Y3 G                {  g0 F+ R. j4 j  {& a/ g- m& z# e
                    if (numw[i] != 0)
2 ]3 c$ H2 u: L2 X! R* I6 x                    {* `  o- l: P; S& F9 X
                        i++;2 u0 s4 V* h- p1 d0 M
                        k++;2 g9 ^4 a$ f1 Y, I! }7 R
                        if (k == n)
7 x4 y0 P( _1 Q7 @                        {, _) J+ I% T! k5 d$ Y: p
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了0 l) K; I  \/ j7 b; \
                            k = 0;- u8 f. E4 X9 ]* \+ w. [
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
3 U8 J1 o: h3 F* B, b4 `# `                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
/ c% y5 [% K6 ~                        }: I! N" z( u. M$ g5 j1 d' K3 I
                        else//输出暂时还没有改变数组元素的值! m. e# `' i! b
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);9 f9 V% }' T9 L; x( [4 E
                    }- {/ C5 X0 g. U9 R6 N. a% R
                    else4 V. L$ h, f/ V% R  e" h/ ?
                        i++;//数组元素为0,直接跳过,不计数。。。
4 ]- P& v. z3 W/ Y: G! ~6 ]                }4 h9 P: E- \+ O' u. Z
. I* n0 `+ M8 J8 M3 k5 E4 K

  Y4 @: v2 z4 T            }//结束while循环' U/ B3 Q. a) B( {* R, |, i* g  ^
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦" p# Z/ p+ I# Q) Q. e$ k1 m; p
           4 L* c  h1 R* j4 \7 i
                if (numw[i] != 0)
1 m' V& A% x/ e' A* b0 n                    Console.WriteLine(numw[i]);
$ d6 R5 }: o( r) L0 J! P" }           
3 _- C' j% Z( b* E7 b5 ]            Console.ReadLine();
( D) n* k7 ^5 s4 N        }% R/ k5 T8 f8 t  P
    }) d; V# B# V7 m8 ^; p$ I3 N4 v  a
}
8 d$ U; v# s( }6 ]  k9 X0 H9 @! 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, 2026-3-10 22:15

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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