鱼C论坛

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

猴子问题

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

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

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

x
大家好!
1 y$ w9 ?1 l8 N: o" {: m这几天我在忙着编一个问题,我用了一种方法编出来!' k* p; p# x8 e8 T
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
  L5 f& Z/ h5 Y4 d" k注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
+ j$ I3 e! C6 b) D/ }) N7 \: S9 i. M$ T. F) b

- E3 T7 s# Y6 w2 C  u0 E+ Q
                            题目
7 P# I) c" k5 S山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。, `- x# R8 I; l: T$ r
第一种方法:利用循环链表
* D+ }$ Y! D" c$ V4 h& W#include<stdio.h>
2 J3 b$ x" [; o1 c: v#include<malloc.h>" `3 j5 ^3 \' C" f
#define M 8            //共有8只猴子4 Y( i8 d" M0 j% @& ~
#define N 3            //数到3只时退出第三只3 B) s& ~! q0 l/ a6 q
typedef struct monkey
% q( e3 X  C$ E7 I' u; T{int number;
& a) d! A, K& ?& v0 h; u/ K3 a; lint flag;! e5 \  {1 W/ }6 u& l( E
struct monkey* next;4 `% T; E* e1 J" i/ |/ h
}MONKEY;+ V* W) P+ {4 l0 v" Y; e
main()6 [% ~# p. s. N  F
{ MONKEY *head=NULL,*p,*s;& m) c  w/ j3 E! L' x
  int i,sum=0,count=0;' C- R/ G5 J4 l3 t
  clrscr();              //清屏
+ p4 f: W. X  l6 N6 {8 ^  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存  t: X+ Y  |$ c# I" n; i0 q5 I
  p->number=1;p->flag=1;& |7 W* e: w+ D. }# V( l% u: g
  p->next=head;/ w/ w9 \- c; I! N0 f
  head=p;
; B' l9 C& J* i  for(i=2;i<=M;i++)
; F6 F- Q6 ]. `, H9 S6 F6 ^& q    { s=(MONKEY *)malloc(sizeof(MONKEY));& r% O# v) s* `/ R% n% a, H
     s->number=i;s->flag=1;( o7 K/ ^" Y% L1 j& ?* e
     s->next=head;' p! A; ~2 i+ m) z% m3 I0 r: [& @
     p->next=s;p=p->next;
# K; l5 h3 P/ N' S6 F9 J    }
7 e4 ?$ k$ c, [6 e) [    p=head;
( z, R4 M- {7 [5 [. I   for(;;)
. D# l) c1 `1 o    {if(p->flag==1)
+ j) A% x. a% k2 p5 }, w2 j       count++;0 x( v9 d8 S5 M( E
     if(count==N)
1 P. M8 X+ V2 D) B! O) q# X        {p->flag=0;9 ?& O" u$ o* Q2 ^" U
         count=0;5 Z8 i* g5 q: ^5 t- f& m$ |; d
         sum++;}
  {# ~2 ~  H2 }4 S     if(sum==M-1)4 A( p; y# G4 D; J6 R1 S7 m& g
        break;2 c* }7 D5 s2 X; k+ S5 B
     p=p->next;; I' V: \4 z/ i3 Q
    }/ F9 s- u, H  q+ K/ M
    p=
8 }* }7 O9 b$ O! ]7 n3 @2 ~3 K5 ]    head;
) i0 h( @* q( E. j) a2 l    for(i=1;i<=M;i++)' O$ l$ G8 J8 a
    { if(p->flag==1)
: U( z+ L' i4 ?. G3 `0 C4 m, \        printf("\t%d",p->number);
' ^9 ^4 d+ W; L. Z" W5 N" u      p=p->next;
- y5 a/ ?& b, d9 g: R( L0 b$ j2 b    }0 [/ V4 |, V& j& a$ d) M, Y

- d0 ?2 G: H+ j
0 ~2 S, K: i+ |1 A2 Z' c1 m' i) h, f6 E1 |* P
}
6 d, Z  A2 ]$ {: Y
第二种方法:数组
  ?8 ^( j0 W7 a+ ~+ `#include<stdio.h>) A) D9 R2 ~- g2 t& N8 _
#define M 83 G4 V0 `# U* o# @# t, J+ ^7 m
struct monkey2 n/ `* f* w! _0 y( y, N
{int number;
; d; I/ N* K0 x9 Gint nextp;
1 E) L1 `3 z* G2 }  u$ D}link[M+1];( Q. m* T7 S+ J7 z- V. r
3 @# q, n1 V# E5 B! V1 L# R
void main()
3 n) A* r& a: K6 H+ Q# n9 o) `{int i,count,h;
" x5 Z9 Z! y" P& Z) n) \for(i=1;i<=M;i++)/ }% l  L" l) D) X9 x# V9 o
{  if(i==M)
6 E2 K: |$ F$ H) S: S   link[i].nextp=1;3 H- d4 f3 Z6 `: q& S
   else
4 j  O) K. g. Y. Z8 U   link[i].nextp=i+1;
- Q6 l. U. c1 A/ b& g3 X" p) F5 I  link[i].number=i;& k5 r, K3 g0 R
}) C: F; B! Y2 l  [" W
printf("\n");2 b/ L0 Y* A% w# a. |
count=0;
; @0 Z+ ]$ a9 w9 bh=M;3 d; ^% W) [# M, w3 f
printf("依次退出的猴子: \n");
& W# D1 A! w# j; W# e! h' Uwhile(count<M-1)
* s- c9 V$ d: _) u& t* n. t, e{i=0;+ ?6 F2 `$ i9 d
while(i!=3)4 {) m- z* r! F% h0 l/ J
{ h=link[h].nextp;# g1 L* j& _9 L" R; F$ {; `5 O8 M: o6 o" k
   if(link[h].number)$ V! B& E& M+ [3 o; O
     i++;}
; O: k# p2 e" m5 a
' _5 \  G8 t: T) sprintf("%4d",link[h].number);
1 _) S" m" o0 J3 |; H2 Llink[h].number=0;# T! O3 c+ v7 g9 p8 K$ i6 S3 k
count++;
; W8 P& m' t5 u/ U0 q% b}& c- ]: L' ~) S
5 O' Q1 q/ q0 d6 ]% y
printf("\n大王是:");
/ S- P& V* l& v' V  for(i=1;i<=M;i++)
( v! \# g( G7 k  if(link[i].number)1 k3 M$ F  t+ Q: C2 M! _
    printf("%3d\n",link[i].number);
6 m- B3 ?- O. O; s
0 C  j& G8 w$ a; h8 J# k* G! B5 d1 W4 z1 t% M
}

/ }) Z. E  v5 E  r: V1 {9 u第三种是普通方法for循环
0 _& S6 {0 s1 D3 Z( O
#include<stdio.h>9 O4 m- ~' }$ G; b  n
void main()
3 [9 C& V( a: c( @{ int i,k,m,n,num[50],q,*p;
7 V4 {/ y' ~2 z6 [* y    clrscr();) l3 P2 z3 l, Y" S4 Q
   printf("input number of person: n=");6 \! r  W7 _% ~. G3 p# [
    scanf("%d",&n);% T7 V+ p! t$ C, r3 j
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
# l# f& }. m7 ?0 S; p& o( o    scanf("%d",&q);
9 e+ F3 H! z( Q' O3 B+ ~   p=num;/ F" u" [6 O/ q  [
  for(i=0;i<n;i++)9 L; G2 m- Q7 }, {. d
    *(p+i)=i+1;8 |4 w5 W6 G  N! C8 h9 B3 |! D
   i=0;
. M2 u+ L/ X# D3 s8 {/ X. o$ w/ I   k=0;3 u: j7 H6 W# c& L9 D6 r* t7 s
   m=0;
9 ~7 _9 \. {8 A+ e. X. }  while(m<n-1)6 x2 N' |  y' K8 ]' F
   {if(*(p+i)!=0) k++;
- l, y- i, ?8 G: a     if(k==q)1 N  q0 C: H9 U) W, y8 T% @
      { *(p+i)=0;
- d9 @$ R7 ~. v/ N. T9 D        k=0;1 J" }& T/ M, |
        m++;) |3 i# E2 W: U- d# @
      }
7 O* ?( g2 t, Q) F    i++;
6 p, n/ q  l4 a2 p! D, g1 u8 @    if(i==n)i=0;* y; [) i9 V6 [! i( D5 M1 d
   }9 q5 u  y) L, E6 F: J# U
  while(*p==0)p++;
( c' A! ?5 F8 J. ]8 u    printf("The last one is NO:%d\n",*p);
: E5 {$ m, ?' \* G- k" G: d     getch();
& k! g* T9 }+ p" \7 n/ S. j6 ]' e
8 P- k7 D2 q& ?! C- M2 d# y}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;6 n3 C' N  `% U4 H
namespace 又费马达又费电" D7 L. |& j1 i4 X9 A
{1 Z. a0 c4 N( y8 Q' j8 U+ g9 V* Z3 i
    class Program3 b8 J+ C% F# ^, V- m* K' p/ Y
    {
& o( m. M+ E( d6 p9 V6 W+ {        static void Main(string[] args)# q4 R  D. N& U- I1 \9 w, w* L% ]1 o2 I
        {8 C) _4 e# l# e* D( ^4 u8 o% t
            int m, n;
1 z+ x( M7 n) [' t            Console.WriteLine("请输入数组长度");( j2 a  t5 @4 v" P
            m = int.Parse(Console.ReadLine());//m为数组的大小) K3 S" w# `% A
            Console.WriteLine("请输入要截取数字的大小");* p$ s! d. W( N1 ?8 X* ^/ y) C# [
            n = int.Parse(Console.ReadLine());  ?5 _) E6 ?1 \! t& P, m, \$ _5 G2 t
            int [] numw=new int
$ b% t8 Q$ [: Z5 [3 V8 m! a
5 ~7 i' a( D, j9 w! }- Z. O9 ]$ g&shy;&shy;&shy;;
& q. z  F5 D( b8 ^+ K            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
4 ^. m# K: _, Q, i3 W& w6 Q2 `            {* y1 a5 T9 B* Y! u- B
                numw[j - 1] = j;
& Y' c( u/ J% ~: f9 g& v2 D' H            }
5 g0 _: h, M& q# n" @) D0 J            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
) \# U! y* m( w7 `4 P- O            while (d != m - 1)
4 w1 i& u2 B& r1 U            {
. H- Y# l  ~1 x                if (i == m && d != m - 1)* k. |" w0 x+ ~/ R0 X2 B  D
                {
( n2 X; Z3 s2 u5 D                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!5 K1 s( ]. W5 f+ X: B7 w- I; I
                    continue;
6 ^% ]6 K& q( g$ f! H. J: h                }
% ?- D) c' I  D                else. W' u3 B5 K7 k4 T) ~
                {
$ d! J; }; w1 W2 C) y5 {                    if (numw[i] != 0)! b* p7 v4 ^/ Z6 m
                    {
' f+ A$ V% ~4 }5 ]! H8 U+ v                        i++;/ ^9 i  n8 f3 \+ v) O
                        k++;
# c; W4 j! I" r4 G                        if (k == n)8 A4 \/ s) f7 {( s+ ~
                        {. T$ |( _4 I, I  Y8 ]
                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
& J( x3 h; c1 f  E                            k = 0;
9 x  h3 p( U5 y) y8 ^              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1  [4 Y, r( |+ I. ^* z# i
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);  W: @2 V: a" |6 i
                        }
7 |8 g3 H4 V' L& G- B- Q                        else//输出暂时还没有改变数组元素的值
! i: e+ z8 ?2 Y  @) G4 {                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
, o6 g$ n7 p9 ]9 ?' u/ [) Q* B. r                    }
( h2 j" H7 O! v                    else
1 @6 A0 E& K3 S" U2 ]4 C                        i++;//数组元素为0,直接跳过,不计数。。。
' E* z- Q) {; ]& C                }
# k6 h  ~$ {7 G : d+ i/ x; P3 @5 q
3 e- e9 D4 d6 I  }' k6 a' {
            }//结束while循环
. s! {! n. Z/ k; n/ ~  J  Q            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦; [3 b% C6 y7 w$ a
           
# N; w5 V1 p* {3 `                if (numw[i] != 0)8 Z% [6 U8 e9 ]" x$ @/ Y! }# ^
                    Console.WriteLine(numw[i]);
1 k8 e/ I$ i( p) R* w. {           0 c8 l/ K% Q! d( s. `- {9 Q
            Console.ReadLine();
4 x5 t- X# Z1 h* V        }
( `: p4 L1 j! ?# I2 B/ q    }
/ l. w( @, _) X$ T}5 U* O8 w& ~' W' _, o8 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-7-14 08:41

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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