鱼C论坛

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

猴子问题

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

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

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

x
大家好!
, h/ F3 k  F7 }+ e5 Y: L这几天我在忙着编一个问题,我用了一种方法编出来!
7 I/ H8 [- L' r- c+ s但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
% _! A8 V1 C* M/ g注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 " }; {; L; n/ f* w$ _, B% J. P

* o# R$ \: F: z0 v1 w; m2 O( J0 u! j4 X! @
                            题目) C0 `0 p' Z& x7 m* u
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
$ y+ _! b6 B* I第一种方法:利用循环链表
( k6 z. C2 l2 _  J8 Z#include<stdio.h>
* E4 b3 d5 R0 n2 U' @+ n#include<malloc.h>) t' S- C2 M1 i$ N1 w' |3 I
#define M 8            //共有8只猴子
( o( Z; z$ g! y: U' T& ~#define N 3            //数到3只时退出第三只
# x# Y7 A/ w8 stypedef struct monkey+ i& E& J# O5 f/ a$ s, A
{int number;
" r  B' ?5 d9 N) d& ?- ?int flag;
% [0 @8 G$ c' ~% m" bstruct monkey* next;/ X% _3 \$ Q5 t$ Q* u7 X3 J& w8 H
}MONKEY;
9 i* M6 K7 R- O2 ?% }" v- v9 umain()
5 Y% w1 t3 k7 H% @) x{ MONKEY *head=NULL,*p,*s;
( f" B$ k; u+ d5 @8 y1 l  int i,sum=0,count=0;% S7 ]' w& V; ^$ y; I
  clrscr();              //清屏
  o# X1 o, W4 h) J3 ?  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存- f9 ?( n. j  }& K- d
  p->number=1;p->flag=1;; D1 {& t7 W7 z' A$ u/ v
  p->next=head;7 x9 E7 A0 {# S% `
  head=p;% M' n8 S$ v8 R3 |! Y) U; H
  for(i=2;i<=M;i++)/ e# y+ \1 y9 ~- r) w- u
    { s=(MONKEY *)malloc(sizeof(MONKEY));
: k# D( P; E$ b     s->number=i;s->flag=1;4 Q& g  `) N. L+ [; h
     s->next=head;$ S, e* B* G( p2 z9 O& K
     p->next=s;p=p->next;* v, ?2 c1 }# m! ?2 x& x
    }
. E7 y/ E! G9 Y# L* m0 T$ Q    p=head;
; z$ E$ X3 Y" @   for(;;)
( o& t. ^( _' W6 d4 j    {if(p->flag==1)
$ M- P( }1 w2 W3 G: j- p% d       count++;3 f, i6 P/ h  @1 [8 @
     if(count==N)# m6 v8 ]& X: c
        {p->flag=0;
3 s8 F6 O) Y# q/ \         count=0;
0 n6 j: g; G- w: G# H. }         sum++;}
1 z- q& I" F3 F     if(sum==M-1)7 X) E* Z7 ^; U: k* L9 g7 [( O' B# ~
        break;
4 P9 ^8 e% S" W3 R; N1 m     p=p->next;
; [. ~. e3 q' N# \# M    }- ~8 o7 ?2 N$ w- B; L; @0 k
    p=
# D4 e+ W3 h6 `& B  `    head;. l; B  u" {9 X0 ~, p3 T
    for(i=1;i<=M;i++)
4 s' a! h) m2 x7 }- }$ V7 ?    { if(p->flag==1)
# i' X$ u$ m' G        printf("\t%d",p->number);
- m" z3 T/ G% o      p=p->next;+ Q. @+ E9 O9 l! }
    }
( b( M/ u5 U, B4 R$ `- M; a! U  g1 I4 T6 p- k, V

: T0 G% `2 J0 O8 S8 |$ }! |0 }8 [5 L$ W
+ N! D. [9 E9 A2 V  [5 M+ {}

0 g, f! D2 F& x, x第二种方法:数组
" C/ K- C! \0 _# P( y( n#include<stdio.h>
4 R- s/ ?) V  c! e9 I5 i" n#define M 8; J7 ^$ o8 B  c0 N" K, i9 n
struct monkey8 p/ }+ {3 S( m* K2 y
{int number;
# t0 H/ x1 R' {int nextp;
8 Z: l$ I2 ?0 b& q}link[M+1];
5 N) y( d+ h: F( [9 R/ h  Y9 i3 u/ n+ \  C
void main()$ _9 T" ~$ W- F- w
{int i,count,h;
% u7 {3 _% K1 A+ v2 e5 a. o5 Gfor(i=1;i<=M;i++)
# b# H- R' @5 G5 X{  if(i==M)) e1 g; g# Q2 O# b7 Q8 ]1 s. U
   link[i].nextp=1;
, w' `8 _$ ~) Z  U   else
6 M5 G* J0 x. z( T' e. g( t' O   link[i].nextp=i+1;8 f9 |# u* {2 G6 P2 u
  link[i].number=i;
' B4 T; c6 ?5 b# ~: F  j! W}
1 n: M+ R3 Y7 a, r- zprintf("\n");
/ {9 C# I9 f$ Rcount=0;4 y6 \4 u1 I* j2 c9 v
h=M;* i$ p. S/ y+ s4 T1 J7 Y8 K& K. c
printf("依次退出的猴子: \n");- O* Z! ]' w* b- b2 \7 {; Z/ V
while(count<M-1)! x0 h- q* M8 h, m5 p6 C0 L
{i=0;; R/ m  _4 O8 f5 u: C1 A+ E; C
while(i!=3)
  z, Q6 Z$ H! b4 Q! g  u4 _{ h=link[h].nextp;
5 z# N2 _% h9 L6 p2 a4 x% @% y   if(link[h].number)
3 o8 X+ a- X: M6 b     i++;}
$ J4 ^/ I9 U7 G
. Q* ^2 n4 H  dprintf("%4d",link[h].number);. Z7 n; Y2 \! l$ ^
link[h].number=0;) q- z9 {& |7 i
count++;" @5 P; J# G# @9 w
}# f# I* }, O! W) Z' @

+ w3 K( R3 C9 \% Tprintf("\n大王是:");
) w& \7 E0 x. Q& a7 n* D  for(i=1;i<=M;i++)7 u4 @: b3 }: Q& K# t& n, R
  if(link[i].number)
# O6 {* G! ~* d- e    printf("%3d\n",link[i].number);
  l0 W" R. Y$ T
8 \* K4 c% `* N" W# w: y( x2 V
3 U. Q8 `1 c! v7 k}

  C* u! V: W/ v, `第三种是普通方法for循环
, @/ h! a  b5 T2 Q/ z/ J
#include<stdio.h>; f6 v) I0 z3 D; x
void main()- l. x8 m$ W; Y& }9 I& I; V
{ int i,k,m,n,num[50],q,*p;
+ c# d3 g; {$ M+ i/ I    clrscr();
$ y/ b' Q% o! h0 I' G$ C! J   printf("input number of person: n=");
' t: d, n% H( O" m    scanf("%d",&n);/ m8 h& H5 o" y8 w
printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只% y9 a0 j1 k. R) N
    scanf("%d",&q);
& a" p3 B) P5 _& G   p=num;
- z" [4 p. D" ?# A/ t! H3 l  for(i=0;i<n;i++)
* n, {0 _# y+ w    *(p+i)=i+1;
% Q$ {( d- F, J6 `7 y7 m9 J   i=0;
6 t+ y" G# E+ ^. s) {. L; D   k=0;
% B6 K! Z& q3 p5 i8 u   m=0;
9 ]5 b$ e9 `, R% |  while(m<n-1)
2 O  \( t( B0 M6 t; k   {if(*(p+i)!=0) k++;
5 q! V" {+ F/ X     if(k==q)
3 n; S- t) E$ f/ O      { *(p+i)=0;+ f; [1 Z' A5 ]( z. a( v
        k=0;: d  b* m8 V& L: f* `0 N: D
        m++;
* C' [. R* `2 }* z! U      }& b3 P& z( @' v+ y* s6 \+ c* i
    i++;
" _0 H1 H% k" U/ y+ b6 Q    if(i==n)i=0;2 X& n/ g, B8 F% |+ ]3 R2 B
   }
+ s. r  Q' N5 U8 ?0 M% k+ K1 G  while(*p==0)p++;
  |3 g  v/ e, Q. B+ Y% `; Z    printf("The last one is NO:%d\n",*p);# {: o* p: P! H
     getch();
, A# F  i8 J1 u( s( }1 }8 V# ?9 |7 p
}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;# ]' F9 i, m2 Q. y# O
namespace 又费马达又费电
8 H  G( H6 @3 N  T- F2 G7 R{1 E) F2 ?2 @, T6 ]; c( Y
    class Program
( ~: Q8 D1 s0 q% d& Z7 I+ s5 J/ E    {
0 b$ J' ~  C7 d        static void Main(string[] args)3 V6 c7 p$ u6 K( m3 P5 J) d6 C* i
        {! X; }  @: f; C
            int m, n;6 _) d3 @& g/ `' [
            Console.WriteLine("请输入数组长度");2 z6 l- _) b1 R* E, g5 [& ^8 x
            m = int.Parse(Console.ReadLine());//m为数组的大小, T4 V: L5 r9 o
            Console.WriteLine("请输入要截取数字的大小");
. d3 _$ q, r$ ]2 }            n = int.Parse(Console.ReadLine());# K! {; J; {9 p9 V$ z
            int [] numw=new int
4 [& I& J& C* b$ G* P% X& ]- j/ |  [! N# A9 y1 O7 e* ^
&shy;&shy;&shy;;
. \2 o8 B# \) k- K/ j  S: t            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数  _4 W' I! F" y4 k. e% t, o
            {
' Y- S8 {2 W- D, ?1 x- b                numw[j - 1] = j;9 m  I0 `  {$ I! R8 [
            }
! g' q% O+ w/ |5 m3 {/ I            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
9 z1 ?8 {; Z- O; A% G' U0 r  B8 q$ L            while (d != m - 1)
7 B& S" I7 W# u. z" ?5 `8 o            {
, r/ j  p& q) Z) h: T* Z" c" b3 v- J                if (i == m && d != m - 1)6 f: U- O- `; a
                {4 U% R2 G) y( x& u; H: u4 y# z4 u
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!  F  h$ i& g9 W4 {% V$ \
                    continue;
/ h) M, v; G  h! B                }
$ L/ m5 M" u! `! ~                else
; l. B: M3 B0 e8 W, G9 \                {
# @, `* S0 d" q7 M, g- _                    if (numw[i] != 0)# [6 }/ c" w* L# c5 W" g' _, N+ _
                    {
* q/ O& z* ^! _1 j, L# I                        i++;
' v9 A) H  U: O                        k++;
( Z) Y7 [2 O& l& S3 Z$ d                        if (k == n)2 K) O$ y' G5 b, w3 S9 \& M
                        {
( U9 B: c8 z& j& Z                            numw[i - 1] = 0;//把在n位置数组元素的值改变了- d7 D, ~" H0 I6 d
                            k = 0;
) }2 D1 q  e( a$ l9 e3 F( B              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1- T) Q, I, q' k' w) U
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- z0 Z' Y9 P2 f+ e                        }
6 a7 Q9 t  V$ C                        else//输出暂时还没有改变数组元素的值
2 Q" y0 C+ s4 C; w  O  {) e" O( N                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);. R1 u  V+ f; b1 o5 n
                    }7 k& L3 i" r4 u) w3 G1 T
                    else9 @1 t( v0 n# s% A* d  l4 o4 k1 z
                        i++;//数组元素为0,直接跳过,不计数。。。
) F" O. p- e/ a  G, ~# n, s/ l                }" J/ m  e) k' ~5 r. \0 U
+ D7 o  h) F% c  M9 i

( `; ^5 s6 C& v. O( A% y4 ^" ?            }//结束while循环3 w8 |( @) s1 d% m& ?
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
, D. |7 }2 [) L1 d, a           : J2 q' B: n: R+ h; G
                if (numw[i] != 0)
  Y, `" a& |/ ~! [; R- Q4 e+ D                    Console.WriteLine(numw[i]);
8 A& ~, W4 u/ }$ V           
1 B1 n# ^" C7 u2 ^. k            Console.ReadLine();
2 R7 Q  v# N% |6 I+ `2 u# c        }
% T; o5 l0 a. z1 M3 L; T    }
1 K: A8 w: J' I: F* j6 y% b# ?}5 Y0 L- M' F: W  ^7 E2 h
小甲鱼最新课程 -> 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-2-7 17:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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