鱼C论坛

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

猴子问题

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

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

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

x
大家好!: d& T, {/ O0 H: ~2 Y' C
这几天我在忙着编一个问题,我用了一种方法编出来!1 h4 W4 l$ {" c
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
( A" a/ n: e! J3 C注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 & K& t; I, f0 a  i" i! o
6 o* h, R/ |% p/ L7 X2 {; m2 ]

; V5 P+ x; z* f
                            题目
( j9 R# \; [# \! `山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
; n% }& ?+ t4 _- O  r# M* Y第一种方法:利用循环链表4 U; @! w+ f. a& H6 Y! z) [8 R
#include<stdio.h>
+ A0 v" p( }9 j* ]5 [6 ]7 y#include<malloc.h>1 s# ~0 f  ]) [9 q) C+ }
#define M 8            //共有8只猴子
4 i/ p$ G& i1 j% I#define N 3            //数到3只时退出第三只# H) l5 i9 g$ ?" |
typedef struct monkey6 l# M+ M8 [9 E% E- A" D+ b, Z
{int number;0 Y0 v: I# H( N: F
int flag;+ W7 w% y& a& i4 w* z3 F
struct monkey* next;3 w' ~5 O7 |, p6 a& q+ n; y
}MONKEY;
* T# W* n' a: I3 k: gmain()
3 R% Z' R9 M: B& s{ MONKEY *head=NULL,*p,*s;
8 }1 }' o' |$ p: {  int i,sum=0,count=0;
9 \7 z  p* l+ b  clrscr();              //清屏
, @; E" e1 I; W  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
/ I8 X4 z# t# t  p->number=1;p->flag=1;( q# s, C8 _1 p0 ?$ I
  p->next=head;9 C9 `  p9 [+ ?- ]! N
  head=p;& e4 h* q0 _2 o, ^' ?/ d5 C6 `
  for(i=2;i<=M;i++)8 {. T, a! v5 R% E( O; y- a+ F
    { s=(MONKEY *)malloc(sizeof(MONKEY));
) ~8 m- A( [! x3 I( ~9 [7 l     s->number=i;s->flag=1;4 D8 u! X5 R8 W3 p* c% y9 Y4 X
     s->next=head;. |7 V. {* y& ]8 G& L+ v9 S
     p->next=s;p=p->next;# [: w* Q+ T& O) p' s, v& |( e9 t
    }/ [3 L' h' y" O; E$ N4 s) M
    p=head;+ K1 S0 S& {) y# I) _0 D
   for(;;)4 N0 M% M! n2 p; V
    {if(p->flag==1)- R. N; B6 R. Q+ f
       count++;; d6 K5 U3 j- M0 ~& A' R$ u% A$ ^4 N2 \
     if(count==N)8 [6 R. p* c5 S
        {p->flag=0;
. u& t# ~" g9 g         count=0;
  C5 c( I. k" c+ u         sum++;}" C' M8 k% A* G6 T% [  V0 X1 [
     if(sum==M-1)1 e; M  [3 \9 l3 B; n5 S, D
        break;& ]4 V7 e9 u& l( D3 J
     p=p->next;7 {# U& f* ^1 P5 l
    }6 E7 m4 n, ^; [. c% L$ r4 @/ O& {: Z
    p=
- n- n5 L. y# t# M$ b- y9 ?    head;4 I* A) ], [2 P0 [
    for(i=1;i<=M;i++)
* j" D1 L5 l' Y$ Z' d3 L    { if(p->flag==1)
0 h) R- D6 k& ~# a1 ?- U0 x        printf("\t%d",p->number);
* K  ?9 M. r9 s. X      p=p->next;
( P7 l4 N6 W9 U! A3 R8 a+ W    }; ^+ o. I2 j! v; x5 }; E1 s1 n
$ f3 f5 }3 k% x+ O" A1 C
; e. d+ ~7 B# a
" H* E. l5 F, z; [6 r6 {
}

* n5 r- i$ S+ Z; a$ `+ b第二种方法:数组! J+ c. a! P# I0 K8 d. I7 @
#include<stdio.h>
; P7 Q0 U, K9 G5 L#define M 8
3 X% F! t% e% @struct monkey( \" Z7 W; Z' B0 b  s: s
{int number;% K" s0 u( c! r9 J1 J) t( a8 F
int nextp;, F* a2 U7 r+ Y% M$ [7 {
}link[M+1];
: h  E6 ?# b- [) y9 \4 S
7 K, d  q- t& t$ O; ~) P$ fvoid main()
0 Q7 c" s8 W: f+ `+ g{int i,count,h;
8 y0 Q( l$ w' F3 ?1 g+ [" m. Zfor(i=1;i<=M;i++)- ^8 P5 d5 w; \: p" A% w" d
{  if(i==M)
) ?1 L& W9 C0 \+ L, D   link[i].nextp=1;
2 Q5 d0 s- H2 J" t+ C   else* Q: D, \/ a* V6 U
   link[i].nextp=i+1;
. u7 B5 H+ Q2 L7 h* J0 |* I  link[i].number=i;0 n5 u, T# Z- |
}
* B; l9 Z; H. ]% s/ p/ \1 F& kprintf("\n");5 G  Z' h. H) X) R7 h! w6 L2 N
count=0;4 t1 c2 F: \/ M
h=M;& }2 {7 z3 h6 v$ u+ t8 e
printf("依次退出的猴子: \n");
+ ~4 R' Z  _  C* P0 ^. }while(count<M-1)
+ B7 v, T  W& I& i7 D7 E{i=0;5 s% w' Y/ W" v* w1 w7 ]
while(i!=3)# H$ C9 d! {! Z) }0 {8 i' [/ ]! Q
{ h=link[h].nextp;
' Q& }$ V; v: k+ p' ^   if(link[h].number)) T9 K4 [% D; o. z& W
     i++;}
% a/ M& ]$ O& o  o: ~
& v2 m1 ]  \3 y" P8 |printf("%4d",link[h].number);* m* k# I6 G2 n! ?) f
link[h].number=0;
$ e5 B# v, C6 Y& W! l6 d- v( g2 }count++;. i7 o+ t$ ^- ?/ R
}
. f2 E# U+ }6 ^% T6 i: ^7 w1 k
5 I  X3 [) u% q  O9 p7 f$ e/ _printf("\n大王是:");, r4 q7 d. D  Z. Q0 V; N. Y
  for(i=1;i<=M;i++)
8 t! ^1 F  ^$ R# k0 j! ^; J9 i  if(link[i].number)
0 p5 _* F- N+ C/ \, x% p    printf("%3d\n",link[i].number);
( R6 ~6 O6 K( n8 S
, C  ]' J: M, w; B6 e$ k7 q; |1 {3 |* a
}

) T0 y4 M3 b- Q. K( }1 f第三种是普通方法for循环

- t- p( z- m1 ]: R, Z' L. Q, T#include<stdio.h>- j8 E+ U0 `' Z3 \' @
void main()0 v" Q; _! {) b
{ int i,k,m,n,num[50],q,*p;0 g9 a: M! P8 Q# P  U
    clrscr();7 I/ [4 H& S5 j1 A" @0 ~3 T
   printf("input number of person: n=");- G" p5 H2 k; b4 [  U! B4 h4 @0 {' d
    scanf("%d",&n);$ _/ `. y) W$ l
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只) k  ^5 h4 h# c! k6 F8 X& M5 p
    scanf("%d",&q);
: d) h/ x& t8 k$ d7 K" i! `" L   p=num;
, |0 e+ F- G4 h: r1 U$ F  for(i=0;i<n;i++)
1 r2 o" m: _4 k% i    *(p+i)=i+1;
! B/ n; W' C- V: n. D$ c( \/ o& T   i=0;
) C7 v+ f2 @+ ~, Y9 T* w   k=0;
3 M7 u+ y, _' G   m=0;
& b/ k+ w. W3 m: M# M  while(m<n-1); ]/ q* ^& O4 v% A* v
   {if(*(p+i)!=0) k++;0 Y7 ^. g% |" n2 ~+ h# D, e
     if(k==q)# u/ y( W1 R/ s+ L" V* _/ z
      { *(p+i)=0;
& _5 G" x+ ?/ e        k=0;
2 t% {5 R& `! u& n        m++;( J: O2 v- J. }7 E0 Y! X5 Z' Y
      }2 h+ E4 E" \# v5 z8 w1 O  I7 ?
    i++;2 _/ x# e- q7 H! y8 F
    if(i==n)i=0;
/ q0 k# J2 L& q$ J! ~' k* l6 _2 Z$ P   }# l8 G/ A* E" _0 ^9 J& L8 k/ _
  while(*p==0)p++;
# D' G' @% `, i2 H- M( |    printf("The last one is NO:%d\n",*p);
7 R: ^- n6 z9 [     getch();
! C& d5 W( U" @1 G) W
, F1 J. Q( t: o' k}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;9 t& M0 R. ^$ U) G: u
namespace 又费马达又费电
3 [9 I9 c0 Y' M2 l1 j% B{
3 A' u5 X* u9 f0 a( L! V/ v    class Program
( N  p# ]. g9 q  S1 z+ X    {( p" T/ [% m( v5 m1 T
        static void Main(string[] args)+ w) e6 G+ k0 {/ C1 r) V
        {
2 [; j* p0 O" @+ t  H. M            int m, n;
8 Q# n4 ^, u$ j' t: a0 t+ f            Console.WriteLine("请输入数组长度");
/ j8 k! T( n+ y+ U            m = int.Parse(Console.ReadLine());//m为数组的大小
  Q* k& c% l, n) I, y( p            Console.WriteLine("请输入要截取数字的大小");
7 w+ L0 C4 l/ i) \$ j            n = int.Parse(Console.ReadLine());$ ?% }; _5 V; }5 ]- A$ m; i8 T$ S
            int [] numw=new int' U2 f! T2 a9 y: S
6 k- X- C9 P% `
&shy;&shy;&shy;;
' M' |6 T+ C1 z" _# R            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数9 ?! C2 W1 W/ `
            {* {/ I& q, y7 u/ k
                numw[j - 1] = j;; E! _0 `, h' I- W
            }3 g0 ^1 t7 x( d  o0 D  o' m
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! W4 o* |% F( T1 t# C1 n
            while (d != m - 1)
* k4 H( n2 Y) U* z/ K            {
3 Y6 ^0 g6 E# z" f4 R# m                if (i == m && d != m - 1), O& p: x. E7 K4 \
                {
( u4 E! v6 X0 H                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
* [; `9 z! X, ^2 ?9 f                    continue;
" `$ a6 X; Q2 Q% U7 c( a                }
+ Z; S5 u+ {! ^0 ^: l                else! x0 ^, j8 |$ o% n7 n! a+ S
                {, P4 n/ N/ l6 t
                    if (numw[i] != 0)
( q7 D  O5 }9 f5 Y                    {
3 t: w6 v0 Y' P# A( t( B% Q, C                        i++;
( A, T* @1 j+ H8 S! p- F                        k++;! j, j5 N9 p. o5 O% U  t9 I
                        if (k == n)" [$ p( m5 l7 O  Z, I6 V8 b
                        {
# B7 t  K6 W2 e  w3 K                            numw[i - 1] = 0;//把在n位置数组元素的值改变了" G! ]* w" v8 ^3 l
                            k = 0;
6 ^0 X  b3 Y% s* Y7 `              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1' ?5 a! f- x& ^: M
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);: U. o" f. W- I! _* q% B
                        }9 `/ C5 a; d2 I" u$ u; E8 }
                        else//输出暂时还没有改变数组元素的值
: b' k3 m& d% q* a& n# N: P: u; q7 |                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);+ X* h6 Q, a3 Q
                    }
; t3 y5 l% B: H- u- l! |9 n: h                    else
. N, F) Y* l& a                        i++;//数组元素为0,直接跳过,不计数。。。
% ?8 [; Z3 z2 o3 S9 c2 }                }
' H% g4 ~# h/ L. w
4 S  H3 P- r; _) x7 v0 |8 v  h: j& a! c* X/ J
            }//结束while循环
9 E0 `% b2 Q+ q! i9 o            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦3 B) S' d3 M7 z! U! a
           1 j* }9 T8 B1 A( A1 `% m
                if (numw[i] != 0)$ ^+ `3 u/ t2 e5 Z2 W- h
                    Console.WriteLine(numw[i]);
% s4 j5 n8 H: C, e6 V           ( y9 A! D) D' J* w
            Console.ReadLine();
5 F# e6 S# B  E1 J& T        }. z# A8 }6 B7 E8 U
    }
1 E1 f4 t: F" E. k}
1 s. H- H. d) C5 g$ ^8 V
小甲鱼最新课程 -> 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-6-11 02:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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