鱼C论坛

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

猴子问题

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

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

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

x
大家好!+ `2 F+ K1 U% G$ f! m
这几天我在忙着编一个问题,我用了一种方法编出来!
3 _# ]0 v' }1 f3 p1 J但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
7 {3 P& x1 `$ |  g注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
$ A+ N9 L$ m' [# r% p  ]
2 _- G0 M0 w: Z+ r3 B0 H# A
% b% G0 S- O+ h$ ?$ R
                            题目8 E- }0 D" R0 C( C
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
% `( \0 h$ j% h# ]6 O第一种方法:利用循环链表
, k& y7 T; q/ `1 N#include<stdio.h>
* n! i9 m; t  e# y' u, J#include<malloc.h>) e* I# [6 _! E7 E% ^; u& o  e; M
#define M 8            //共有8只猴子
1 k4 h/ ?9 p0 c0 W, f, ]#define N 3            //数到3只时退出第三只
0 m" M# E" S/ ~. Itypedef struct monkey
2 P9 K  v8 `" ^) B2 W( K{int number;* a& A- }" S! s
int flag;
: P+ @0 V, J3 z% |! Gstruct monkey* next;+ X7 `& X( m% G$ s- Z5 a
}MONKEY;
& b0 h: u; _2 P9 h; |3 M# P- pmain()5 @2 K# ~7 P) X" q! N" V$ ~
{ MONKEY *head=NULL,*p,*s;
5 L, x: I' O3 D# T  int i,sum=0,count=0;0 I4 o$ l: R# `7 N* k$ l( A
  clrscr();              //清屏7 k# g( f1 I  o( n+ i8 O, ^" M
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
  V, k! W7 M) L7 O/ M# R) G+ T. T  p->number=1;p->flag=1;
9 a9 q" c8 j6 w& c- r0 \  p->next=head;
( C" g/ V9 K2 s& H2 K  head=p;
2 ]+ ?1 L# g9 U; Z# J8 H: [  for(i=2;i<=M;i++); J: _6 s+ ~( Q8 v+ E5 u' A
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  P+ {+ |+ \  h0 X     s->number=i;s->flag=1;
2 Z+ R! ~3 ]3 p; h7 i9 j8 C     s->next=head;' e$ Q  y. P4 K) K7 l/ w& a
     p->next=s;p=p->next;
3 W5 V/ l  H+ ], k; T    }; E* `  F7 L. [5 v
    p=head;
; k/ g$ Z+ C( h9 L   for(;;)" v0 f* B# x( s6 m7 ?  B, }
    {if(p->flag==1)( i+ G4 F' F6 [+ N
       count++;
! J0 e( U% X) e( F( h. G     if(count==N)3 s7 m- G2 j+ J5 i4 s# l) F. Z# C
        {p->flag=0;
8 b0 z: [7 M: e2 z         count=0;* J, }, O# L) W1 q$ H
         sum++;}8 y2 A6 e" s6 M' b) W  g
     if(sum==M-1)
1 @- }! h# ~7 f# H        break;6 q$ g) P; _0 u% m; q' l4 f% {
     p=p->next;
5 B- x7 }( W5 j5 S+ m, b$ A    }- b0 f2 G" ^+ B; s- A& G, a: u1 b
    p=9 F3 V) L# M) K% R. \
    head;: C- O5 E, ?2 V0 W' W1 K
    for(i=1;i<=M;i++)
, Z6 x- q5 G; E! V0 s( D    { if(p->flag==1)
, j/ d& g" m* N0 X3 Y        printf("\t%d",p->number);! K2 W; S5 x* L! o9 j
      p=p->next;7 K; \8 j- S0 W
    }
$ o: m0 v' Z- G; R1 _
0 o3 Y) `( A, U
# A6 B, J/ U+ X- A: Q
: b* ~/ h+ H. ^2 R}

( I8 {: Y( Z6 _/ k% {9 t9 r' F第二种方法:数组
6 U4 g! w+ `* l6 E: ]#include<stdio.h>
/ X- }7 C: Z: w/ M+ _  d#define M 8
; z3 T( V% z2 [+ v" m. }4 \struct monkey' ~' C  j3 W0 \6 n7 {6 d/ T9 ~
{int number;9 ^" x( D, D! w7 c8 ]
int nextp;
) H0 D1 e0 ], N8 ?$ f* @}link[M+1];
. @/ J8 Q: c3 V; N6 @. c
8 U3 X9 |/ w3 ]  r  i( @7 ]* kvoid main(). H, F, x  C) ]1 ^$ F) J  N
{int i,count,h;' j7 h/ I# b  L% H# s# Z+ n) O: U9 j$ N7 S
for(i=1;i<=M;i++)! h$ }6 N* `) ^1 \! g4 b! |: T
{  if(i==M)# ^3 I  a2 y  e6 {" u7 p! X
   link[i].nextp=1;
4 W; v8 L4 S/ v/ q   else
; p" U' k- D' o: B) S6 z* z   link[i].nextp=i+1;
$ k7 ^& x" S; i* J' H  link[i].number=i;
! T- \0 ?8 R3 u1 T' ?2 h6 l3 C% W/ C}8 E: y/ s3 j* f! A( e
printf("\n");
7 d3 d2 s* y! ]% t7 k, o3 C- K0 \count=0;
* h6 X6 g6 o! s: Mh=M;
* \/ ~5 ?1 g5 s3 e" U% M) kprintf("依次退出的猴子: \n");
* b! x! G& \. n/ `1 xwhile(count<M-1)8 p) \2 u$ a+ ?
{i=0;
9 Q+ C7 u* P# ~; N( w9 Owhile(i!=3)% I: f+ @4 ^* e9 \
{ h=link[h].nextp;: C' H3 m+ }" ?; h
   if(link[h].number)8 ?% o4 h" }2 e/ S* k$ X* W* _9 y
     i++;}6 l  N1 {: ?# N1 r

. n0 y0 w. p% a' A, zprintf("%4d",link[h].number);
6 P$ ~, H* K+ x0 z. u; r6 Z; hlink[h].number=0;8 v) Y, G5 H! a( W; X1 K
count++;
+ l# o9 p2 A- t' P9 c}
# r5 j4 y$ ^; l" U$ O5 ~6 _+ b; {2 y: P, O
printf("\n大王是:");
: d; H9 ~+ W# P2 y  for(i=1;i<=M;i++)
; o  {  C* g$ \) b1 Z6 J; x9 u+ n7 y  if(link[i].number)
  {+ H* Z/ L# n: }7 P9 f, X' p    printf("%3d\n",link[i].number);
" P% e3 }$ d* Q6 l# C
* `; b5 C$ ^/ w; q  ?# _1 X; Z4 N
) }9 |% g' j" A: m# T% _}
9 u/ U& a, F7 ~1 Y* V
第三种是普通方法for循环
/ _$ B) O. o* P
#include<stdio.h>/ U/ y& a6 N2 A) H: [* q
void main()
$ a+ C& f" @* ^$ z{ int i,k,m,n,num[50],q,*p;
% M  B2 E) _, [" ^    clrscr();
& ^, q3 B$ F& W9 V' h' w   printf("input number of person: n=");
, Q4 R' r: v$ u  V2 y& d" ^0 ~, t    scanf("%d",&n);) r) U. P/ |" K& H6 e& j9 K8 I1 |
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# Q; z' a# }3 l" u( G0 G    scanf("%d",&q);& X( w) @3 P! e  f2 A* r
   p=num;4 q8 g) R; r, K: N0 L* k
  for(i=0;i<n;i++)6 X1 k: `* g4 G) V
    *(p+i)=i+1;
- n. K+ q! T3 ^. K2 H1 J: C   i=0;/ Y  P+ M, d  y. W
   k=0;
/ r+ ]" h: Z. K" ~/ Y  T   m=0;
: I) X2 w. q6 c  while(m<n-1)1 v! f/ K" V! p
   {if(*(p+i)!=0) k++;; `; G1 k8 R: W* }7 }$ I4 C
     if(k==q): W9 l5 d/ |) H7 w3 _5 s' k) Z
      { *(p+i)=0;. U8 ^) e# i, m0 W% j/ U, ], |
        k=0;) R% A9 p3 V" `( t& j# ~7 B
        m++;' s9 z$ A# \0 _1 L; K. ^  V! q
      }+ U* Z) {5 c# k( Z8 }
    i++;( f" {7 x0 f' T9 R
    if(i==n)i=0;" j0 ~* B5 h6 g/ q9 ^% [7 ]
   }& H+ i9 E9 F4 V; U- z7 L7 Z
  while(*p==0)p++;
6 B; }5 g5 y7 B  u8 M    printf("The last one is NO:%d\n",*p);
4 M" }% g* c+ c8 a6 t0 l1 N     getch();
8 \7 f9 M2 J# H2 }* c0 f" h7 G1 ?7 A7 i. ]: J
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;/ h4 R5 W9 ^  v8 D, N+ Z
namespace 又费马达又费电$ M9 j1 A: j4 j$ A! O' q! b
{
# O: w. u8 @. O5 Y    class Program
& W2 p" ?) o2 c% E* G) i    {3 _5 p) g) z4 n5 i
        static void Main(string[] args)4 b  @  {9 `, ?6 E, \
        {: g; c* e! g/ A5 M
            int m, n;& h( |" {) T( o( F' k( Q/ Q6 m
            Console.WriteLine("请输入数组长度");
# |# Y  F! ?* t2 ~, }" t; k            m = int.Parse(Console.ReadLine());//m为数组的大小
3 `% X8 k( E8 V* _8 E) k7 t            Console.WriteLine("请输入要截取数字的大小");
+ P& F' j1 B# ~3 I& ]! k            n = int.Parse(Console.ReadLine());
4 X+ O5 R. V. F, L% h7 a4 i) w/ h1 K8 B3 n            int [] numw=new int4 s) w" M/ b; M/ V* _

3 m7 z* l9 P- u' k* l&shy;&shy;&shy;;9 [9 S8 p' H% M$ u* B  {# W+ r  g7 y
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
+ X  h  q2 M. v) z* R5 H0 [            {
- p7 x9 h# c& y$ Z3 H                numw[j - 1] = j;* {) u2 e/ d  e2 \
            }- {2 F  x# M9 P. q6 {0 ]' u; {
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
' R- w( r! I, R. w6 m            while (d != m - 1)
6 _! h( v% I' v- e& x            {
4 D- j3 y9 v, Y5 @9 R4 D  U9 d                if (i == m && d != m - 1)
1 Y- i) ^$ \  W9 d                {8 s, i$ g" `: p  ?$ N) X
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
' W6 _) k5 P% w6 J- Q                    continue;& `$ W9 E$ }$ D! f" }5 G+ C
                }; h6 c: e/ e2 `+ b
                else- x9 ?0 f6 q+ Y
                {! B; u3 b/ Z% P: s, k
                    if (numw[i] != 0)
/ c3 }% f6 u4 _' q/ z                    {( S; V# N6 R; F5 l" }& H; F
                        i++;
% r* @' O0 T% r0 y5 O                        k++;5 `" X+ R. {1 A2 ?- K2 x
                        if (k == n)
4 q4 w( v) H( d                        {
! U; n# ^- q2 I                            numw[i - 1] = 0;//把在n位置数组元素的值改变了9 @) E0 s+ W( X. `, v& |" g4 E6 {; e
                            k = 0;9 Z7 n; S. O7 c1 ]
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小13 s& b- D, h+ E1 {# g
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
2 h- l' Y" b  O6 j3 f$ K) G                        }# c% B) Y2 r# J% p
                        else//输出暂时还没有改变数组元素的值
. b# V+ M( P, T+ E5 I% X) _                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
( N) g8 X  H- I; \                    }, V# r- s  @2 g5 b9 t1 |0 N3 Z0 ?
                    else
( O3 H/ B6 i  Y8 [                        i++;//数组元素为0,直接跳过,不计数。。。6 `' p) U. N8 k8 z1 P. w4 y, o/ y
                }6 ^6 J5 ~8 @+ B6 p

; V9 @# M; a* }2 V$ F) F/ p$ p" a% ]1 Y4 N; f: j2 i+ Z" @
            }//结束while循环3 a0 m3 a, H8 r) G6 S
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 e7 S8 Z5 ^$ a0 x( k7 K. N8 A
           
. K4 w  d5 B4 x, ?8 V1 o9 f                if (numw[i] != 0)% z  a9 c- `& g6 ~  r. A# h- R2 o3 ^
                    Console.WriteLine(numw[i]);
& F$ E: ^6 h' M  C2 m# l5 f           & g  j& k; Z( x9 u. h
            Console.ReadLine();
* h3 m5 O4 L3 r        }
7 [5 _# l# j0 |' @8 r; o    }% M$ B( p5 U( L
}
- L  f. d5 ?2 y+ N+ j( v- D
小甲鱼最新课程 -> 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-4-25 19:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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