鱼C论坛

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

猴子问题

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

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

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

x
大家好!3 y- b* k+ X0 u- K! D6 V6 D
这几天我在忙着编一个问题,我用了一种方法编出来!, A$ O6 k2 I4 J: \
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!. j; j% ]' N+ @; X- N9 y0 @6 m" z
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
7 b8 m. e5 R1 q
) r" ^0 G7 x( ^7 O% o. p8 ~4 d3 D0 G/ p2 ^  y6 Y
                            题目
, K5 u- ?7 P% s% U9 a0 X0 v山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。5 g) q5 [1 a  R* U- N! [
第一种方法:利用循环链表
/ Z/ z2 j# g8 Y; s#include<stdio.h>( s/ R1 y8 X: K8 P# O+ c  @
#include<malloc.h>
  @8 B4 ~, K+ m: r; Z; A" \#define M 8            //共有8只猴子' y# d9 n7 W* O
#define N 3            //数到3只时退出第三只  \  d$ h8 J: B' g
typedef struct monkey
- ^. E8 F( {4 y! q{int number;
# c  I) A1 |' _% r" xint flag;% z9 b( m( ]* w6 k" P( U5 A. [
struct monkey* next;
) M4 m; x, l/ F( ]}MONKEY;/ j4 n# n  ?1 _8 N
main()
  H1 `+ x  R; U! B( R! P% Z2 P{ MONKEY *head=NULL,*p,*s;
% s, I9 `' f% z* ]6 ^( A: `  int i,sum=0,count=0;
4 T  m5 @! `$ f0 U  clrscr();              //清屏0 `4 a9 |0 k- g& Q5 }! y1 c
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
9 S* I: C! y& i. m5 F/ ~  p->number=1;p->flag=1;
* `, c+ Y/ Z- |# x2 ]/ S  p->next=head;4 {8 F$ u/ V' p& ?1 b+ z
  head=p;* w: @( k1 Y* }- H4 i) p
  for(i=2;i<=M;i++)
3 }, J6 t: J1 P3 y: P    { s=(MONKEY *)malloc(sizeof(MONKEY));- s, o5 t# A* n" T) w
     s->number=i;s->flag=1;
+ |  v/ Q5 u! C* K) `. I2 P     s->next=head;, E6 r( b7 }# A
     p->next=s;p=p->next;, K+ E- s$ r& }2 f) w
    }1 p) c/ G; y2 W6 j6 }
    p=head;& c. y' D/ A& w2 b
   for(;;)7 }! [* x) W0 R) j: N$ r: R
    {if(p->flag==1), o' T7 j! k2 X+ }) @
       count++;& w$ a' d& J6 i9 a0 H9 K9 o- U
     if(count==N). Q# |9 G+ s: `! M" K
        {p->flag=0;
! }1 \  t5 j- l, C" K7 |0 A         count=0;7 [& a& |# D2 r# d
         sum++;}
8 y6 |# {$ t5 ^0 L3 A' I     if(sum==M-1)
6 l5 b6 l! S7 S: v        break;$ H  B1 [# L3 ~2 X0 G
     p=p->next;
: y& F2 w" |4 W+ z$ O    }
' x& S# P+ G6 t# K9 M    p=+ }2 S  a/ o" j) u$ s) M' v0 x- v0 N2 I
    head;4 T7 U& G+ @& G/ V9 X0 Z
    for(i=1;i<=M;i++)
) e) B0 m8 Z! W% {    { if(p->flag==1)6 c) s* S" P) D5 j! j
        printf("\t%d",p->number);
% k1 B' A3 v7 \' G      p=p->next;1 s; |3 s5 i  X# G9 [0 ?7 {4 }# ]
    }
2 X* z- P1 c( o2 {) Z: f* [5 n/ c7 \! b8 z( N. m  ?3 r9 W" s

; ]+ L# g6 W  f) p5 s
) {$ M0 R6 k+ B- p}

/ J' F7 q* B5 ], k( L第二种方法:数组0 D0 `8 p; s% |6 T0 |3 \& K% C" S
#include<stdio.h>
$ q- l# v& O0 t4 G% t#define M 83 T# f. ]6 j: e" |% b6 B  x
struct monkey
  ^  S* H# i3 u0 y0 R. ~{int number;- B" y, x' d4 E6 [
int nextp;
- J# J; C. G, w' i1 j}link[M+1];& z1 r3 \$ F5 M# G2 J: a

5 X$ u+ L  r  w2 l  k' V* Uvoid main()7 O+ S+ p3 B2 m& m2 A* x- [$ s
{int i,count,h;% [! t0 ?7 P% L; x. @
for(i=1;i<=M;i++)
  R; {% ?" X, p{  if(i==M)
+ Y2 x2 e! @" Y) ^  f- p! |# ?* o   link[i].nextp=1;( G! Q4 u7 ~0 h/ C7 l
   else! [$ d. S. S2 f+ z
   link[i].nextp=i+1;
. H5 X5 T. R$ |$ ^$ z7 f0 C. g  link[i].number=i;
( h6 M. s6 ?# I% }) n6 w! w}# S% H6 {% C2 S# b2 @. [0 r
printf("\n");# {6 R% H# p8 f0 V
count=0;
% L9 W0 y2 E7 w, L, Dh=M;" s$ h: {6 ~3 L- O2 q  n$ s
printf("依次退出的猴子: \n");' q# q& [7 ]" J1 e
while(count<M-1)
9 x, ?* o- m( @: a# t( `) L2 T{i=0;
% [$ h* ?7 `9 ]+ x3 ~while(i!=3)
5 }% T! I4 z/ \! ^4 Q' Z{ h=link[h].nextp;
, O8 m) i% T& W, z( ~8 V   if(link[h].number)
. N* }" ]. |! V2 c     i++;}3 X% U7 |/ w. e+ b( p

" p$ I" ?8 s( ~8 N& Uprintf("%4d",link[h].number);  v! T6 v6 m( D6 n. e5 D4 ]
link[h].number=0;) s0 r2 S- @3 ^* e" v  h/ ?+ X
count++;+ ~7 g. v$ F% u" F, k* }% q
}
/ ?" z$ ~1 ~7 c0 J0 q5 i7 Z4 N5 f; T: ]3 B8 |
printf("\n大王是:");
( t) K* m. I; l6 b- ~7 B  for(i=1;i<=M;i++)8 u+ P0 k! b3 `
  if(link[i].number)
1 \( X( ^7 o9 g6 i0 J6 c+ N# n    printf("%3d\n",link[i].number);! N! \1 {# ]% L
$ R. W/ e) C5 Y8 j! b: J

' n* q6 N. Z, D( t* L  H}
/ \" F+ A' _7 Y
第三种是普通方法for循环
: T, \/ F" C5 |# m
#include<stdio.h>
- }7 I- p! x7 U+ Jvoid main()
- J7 o0 W" r1 M( Y{ int i,k,m,n,num[50],q,*p;
# L) U( K1 b5 |8 n) \    clrscr();
( H" T, V. J. g3 d   printf("input number of person: n=");! }& n, A8 w7 w
    scanf("%d",&n);5 T5 i, W, Y% D" J9 j5 R: D- f
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
- U: Z8 F% X, S4 W# z0 M    scanf("%d",&q);7 }6 ?! s& I" n/ }+ K, P1 _
   p=num;
9 r6 B  g5 G' E( P% J8 W. _2 Z4 X  for(i=0;i<n;i++)5 R  M/ Z4 T" i( ^% N
    *(p+i)=i+1;' t* @. z9 M0 v3 V3 J9 M! g& v. `3 a
   i=0;
& J0 V) J6 z& T' V* u   k=0;
+ |# j1 o  b; m$ u$ G   m=0;( t0 z, P5 x, o% P5 N
  while(m<n-1)
, L" T. ^( F/ B4 [, S# [" i" E   {if(*(p+i)!=0) k++;
# h$ D  S3 t: y5 a" C     if(k==q)! e& `3 L1 ?8 y' ~5 G
      { *(p+i)=0;$ ~9 C" ?" _! b' w4 ^7 H# {
        k=0;  `+ I0 ]% ^& T
        m++;' h+ R0 l+ X, b* L$ a
      }+ d- Z* a/ _& Q  U. _; C0 G
    i++;% R$ {- ~4 @6 ^" ^  t( s
    if(i==n)i=0;9 s* {! U4 i) y, d
   }4 w6 p. g- M! ~& w. G- m, x2 Q
  while(*p==0)p++;
; j) l$ c4 w9 a" L1 \1 X* J4 z    printf("The last one is NO:%d\n",*p);
! z# G0 _- C$ Y, s/ q: R     getch();3 F, F& M  A, j, I2 F) t
. B0 _4 t3 |* h. y" Q3 a
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;8 c2 C. ^; S$ m' P3 N& a' u# @
namespace 又费马达又费电" }5 F9 ~* i% i2 p
{
' n+ V1 X7 r/ i8 {# K# I  a    class Program, ?# e; U) s2 _$ ?0 [
    {, ]' l. b! y; ?/ u
        static void Main(string[] args)% \& v) e. e, u) K! H; }0 R+ y
        {
2 M* k: R% J  x+ F3 Y            int m, n;; r. Y& O" p1 d4 O
            Console.WriteLine("请输入数组长度");
& x6 k% \6 F3 E, K' l- C. o            m = int.Parse(Console.ReadLine());//m为数组的大小! C, W" k# K9 j/ s
            Console.WriteLine("请输入要截取数字的大小");8 b2 t, Q& b- @. P; A( S
            n = int.Parse(Console.ReadLine());
( c' S& n& J5 h! b1 T            int [] numw=new int
% `2 _7 P' Q8 b: ~' n. u7 e1 q
( p9 K! _- n4 @4 T& ?& X/ k&shy;&shy;&shy;;
/ L: P8 j1 _7 ]            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数- z. T  d3 E( `! j
            {
( G! J  l8 b' f/ F, q3 I' C/ l                numw[j - 1] = j;
) l+ `+ U* E6 ]  [: a/ q! O0 S            }0 y* b" I& z9 I7 n7 u' o  f
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
- m. }& C- J# n' K2 K            while (d != m - 1)
, _: A, `2 f& z% R            {
' q( n( q1 e6 @: s% |. U) d                if (i == m && d != m - 1)$ |1 k; ?3 S( f' ?, R
                {% |! L) j8 o. B3 f5 y
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!7 a& B$ F0 j% o# \/ F2 {8 d! f7 Y
                    continue;
1 c9 `" v4 B/ M8 C" T7 O9 {$ X% S                }8 ~2 G! s/ B+ d
                else
- e2 g- q% Z6 H! }0 e3 F                {
7 I( V( L# W5 q0 H) K- s                    if (numw[i] != 0)
7 K7 q" @0 h  R                    {4 w2 O- ~3 _& U; a  e" a! N, }
                        i++;8 X1 S( |, b* r
                        k++;
7 h7 A0 y1 f5 q, [) _                        if (k == n), M/ x+ v0 D* n! N
                        {
( u) K: j' j9 B  d+ o8 |                            numw[i - 1] = 0;//把在n位置数组元素的值改变了5 Q! S$ a# ]2 V: n0 P3 k
                            k = 0;& p9 Z, f! {* R. b2 d/ ]
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小10 P; f) C: e2 F- y  D
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);+ |; p, }( k% S4 Q
                        }8 R( ?+ z% E4 d: G% }2 |  ]+ q
                        else//输出暂时还没有改变数组元素的值
" j+ q5 s8 @: J' p& n; Z2 ~                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  L8 x$ I5 V& D/ l
                    }
! a1 i8 I% _  i0 N4 K                    else
* X( j/ u' S- K* w' v# z                        i++;//数组元素为0,直接跳过,不计数。。。
* X7 Y0 V$ ^1 b                }3 b3 Q: e% T# x9 I0 [, R: M
2 n; |  N' m$ C: e0 |$ J! L: M" k
& q  v. H7 L/ z9 \% y
            }//结束while循环* ^  }& N6 |+ ?) a% F( V) }6 q
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
# \: g0 q8 j" K1 i+ P% @           
& \5 s% N. `; v, M- w3 y1 n                if (numw[i] != 0)/ d. K( S" q/ z" K
                    Console.WriteLine(numw[i]);% ]' c; _1 w: y- P/ s4 }
           
- ?# n# {# r5 w& h2 m$ F            Console.ReadLine();
) E4 w( Y: v2 w! l# ^' w- H        }
4 E' T5 y7 t( x6 E% O8 S; H    }. Z2 W9 _- C2 V
}, o& K: g; L* U' L: q5 V* c" f6 m
小甲鱼最新课程 -> 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-18 05:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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