鱼C论坛

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

猴子问题

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

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

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

x
大家好!# v0 W8 c! H# w8 e& U6 v# m
这几天我在忙着编一个问题,我用了一种方法编出来!
4 s; F1 R) m  A但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
/ D. x6 d* e8 z& ?" E注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激 3 `% g1 S' M) [# p$ f4 J
( U5 d8 P* a3 v. G6 @, @

) ?- w. Q1 Z' d: {+ T( e* Q
                            题目
. B+ j6 `1 {' a2 l9 M: E9 a  v山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
! [0 ~$ c4 m2 Z# L第一种方法:利用循环链表+ w$ W% q8 b7 n% t, U- t! D' @
#include<stdio.h>9 L6 \) u4 r( W8 M' ^
#include<malloc.h>
* y! R9 ~6 l' S8 m; W, _* a#define M 8            //共有8只猴子
2 I) s; ^% m: r# o' K#define N 3            //数到3只时退出第三只
( ?* z. Y/ m7 b3 Q9 _3 q- ktypedef struct monkey
: R0 u3 _1 d% J, q* E, H9 f{int number;
+ W& [) Y2 s5 Q7 S5 r8 |" K) [int flag;
4 f% q1 D+ N* @  v/ Estruct monkey* next;9 {, m: e5 M4 k6 E" f
}MONKEY;
, p8 V2 r) [: e/ m4 o4 Z, Cmain()
& P* y& |+ L4 \3 {5 [5 m{ MONKEY *head=NULL,*p,*s;
) s. S" F" B( E$ h. {  int i,sum=0,count=0;
# c1 s3 ~% H0 A  clrscr();              //清屏8 ~8 _( i& D1 @
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
) t. Z9 u, H7 t) D% P: N# k8 D4 P  p->number=1;p->flag=1;
. x+ u+ X- q0 @6 @" i: t  p->next=head;
2 {5 Y: g  r- ]6 q* P  head=p;( c' N/ ^( g9 G2 [; r/ x3 Z
  for(i=2;i<=M;i++)9 N4 e7 N0 Z$ ^8 K
    { s=(MONKEY *)malloc(sizeof(MONKEY));
  N2 V" }# A5 r" L/ h     s->number=i;s->flag=1;4 z1 D: \! |, @6 ?
     s->next=head;3 k9 ]6 u" R) y9 r4 O% X$ f; c
     p->next=s;p=p->next;
/ _9 E- l& t* K    }) ~$ d; d0 d9 n4 P8 y
    p=head;( j; {# B! |1 n% T3 J/ T
   for(;;)
( h) S8 w; F5 I. z; d; \% `+ E- @    {if(p->flag==1)
  y" Q2 R9 m9 y# m6 k4 Y       count++;) E% [) P6 x9 ^2 B$ h" w: k
     if(count==N)
  e. h. Z+ U& A/ c" V5 d/ u        {p->flag=0;
; o) H- X$ d' Q4 q         count=0;3 q! V1 s$ e- G8 \4 u0 g7 x
         sum++;}
& N: ]6 {5 X+ w* \% E0 \     if(sum==M-1)' {5 ?" ~4 C+ O- B( H
        break;
6 L& ^% e4 v/ C, L, N     p=p->next;% K: n2 J/ F/ @' y# \9 \, M, _
    }) n* p$ C  m! y! c: \
    p=1 q' D' }. t, k) _( A* x
    head;
% Q% l+ [- S5 d9 y" C5 V1 Z+ D    for(i=1;i<=M;i++)
2 C! m9 s8 N8 M6 Y! t    { if(p->flag==1). H/ a! \7 n1 q7 l+ l" S
        printf("\t%d",p->number);
6 h' L0 R! ?# t1 y' t# }9 a( a) n      p=p->next;. N$ [' z  b' a( ~
    }7 w) Y; Y4 s8 G2 m4 c4 [

( z) H; I8 ~4 n- h: s( p. u' G( g8 T; M: ?. \" o

9 i+ r5 c! C7 g8 f) c' q3 H. L# K}
, ]* K, n0 x/ A2 Z/ g8 O) v
第二种方法:数组
5 E" F  m  V, ?. a( R#include<stdio.h>- s/ p0 Q9 i+ m) G
#define M 8
5 T8 Z0 H  A7 }9 k+ ~) E* D8 _+ x. Nstruct monkey
0 E( N: W3 i  F6 Y4 O! P1 u{int number;5 U# [( n5 G9 q# y' `3 K
int nextp;
  e0 X7 f& o! m- G4 D5 S  Z}link[M+1];
; w& c- k9 d% c- x4 V/ A# }  a; P2 j5 y! S6 c# n! ^
void main()$ Q" E2 d1 q6 `  L+ B1 A
{int i,count,h;
  ~8 w' Y' `- T$ V' Z0 ~for(i=1;i<=M;i++)0 a) i- q! `8 u  o2 ~) _
{  if(i==M)$ T1 S! W* p4 F1 D) \7 F
   link[i].nextp=1;
0 E% o# @6 M% B; y# c7 j4 K   else( f' Q; {: i) `( c
   link[i].nextp=i+1;
7 N6 y2 z- q: a- c  link[i].number=i;
5 r  G* g% C( }3 [( A3 P, w}
' ]$ x8 N9 S+ Lprintf("\n");! h5 F' B6 F. |9 c  M- q
count=0;
8 _6 C. @. {/ dh=M;
: f  o2 h3 r- U" c3 z" Uprintf("依次退出的猴子: \n");. {+ }+ y7 C6 l
while(count<M-1)" v8 ?" ^0 X- M: ]( f
{i=0;* e/ j, l" Z8 j5 d6 W! D0 L
while(i!=3)
7 ~1 k" f; C' y5 m{ h=link[h].nextp;
: N. s, j8 C5 C   if(link[h].number)
! b  a  a9 v; r, A     i++;}5 @2 b  s+ {: s7 C6 @' _( d+ @7 ^
1 G0 y( ]2 `% N: t
printf("%4d",link[h].number);9 e( N" j) l; k
link[h].number=0;3 e( x7 e& j# a8 I
count++;
' x. h# W7 r  J2 G/ Z! Y}
0 v! n7 ^# B' V1 m  R
8 c3 ~+ p3 N2 R8 z' iprintf("\n大王是:");
$ c  J- E2 O3 p/ W' c! p2 g. S# i  for(i=1;i<=M;i++)
( b0 `9 H: }* _5 f  if(link[i].number)! ?" M7 L  V. [
    printf("%3d\n",link[i].number);
  V7 V# s0 z% C4 E2 T' T; X) S  q# s, R% o0 \, t

0 {) D5 x0 g$ i}

% O1 D4 O1 q/ m第三种是普通方法for循环

* ]; D+ ^7 s3 e/ M7 ~) H#include<stdio.h>* ~9 R; c" b8 Y) B& `8 S9 |
void main()
8 i  Y6 g) g3 B& x{ int i,k,m,n,num[50],q,*p;
2 q' \" a; i/ e8 }; P/ g    clrscr();* q5 i) T# v+ [' m: Y
   printf("input number of person: n=");3 S1 X  ?3 W# e3 ?- d. N9 ~
    scanf("%d",&n);
3 K/ ^' X4 b) ]printf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
, K" E2 _' A0 J6 ~) D    scanf("%d",&q);
5 C4 D3 l( N. n2 B) D+ m   p=num;
  ~1 |+ P) h( \: H1 X2 U4 T- l# G1 f  for(i=0;i<n;i++)) C" i1 }; m$ q3 j4 s, K; q
    *(p+i)=i+1;. m/ A' [1 Z. b8 F# X- ^5 A- W
   i=0;* V: Z4 E2 P' b$ y6 a1 n  {
   k=0;
* |8 w3 s* K9 l: `) G1 F' Z   m=0;
! y) G, ]  R2 n5 T: b; U) n  while(m<n-1)1 Q5 Q# m7 n( ]
   {if(*(p+i)!=0) k++;
5 @& F# H# n" F; \! D- A     if(k==q)5 s6 n$ Z' e! `* T
      { *(p+i)=0;
3 X1 u, ~* M/ A& k        k=0;
4 D- l# ]8 K! \0 |: c        m++;
9 b6 d4 f% r! e$ G+ |% U( |3 l      }
, F' D& U- K- S3 H2 ?! C/ ~; `4 g    i++;
! a) p: X# X8 F. G' K- k* j8 k    if(i==n)i=0;/ {( h1 D# D6 U) n2 j! ]6 i
   }  g. o3 Y$ c+ ]8 i, H1 b8 @
  while(*p==0)p++;, _# I; R7 X* v: U; ?7 y: ?$ W
    printf("The last one is NO:%d\n",*p);
1 W! y1 [4 s4 z0 Q' D     getch();
  k+ u' t$ w* J5 H
, J: f: A/ n& z7 L9 Q- \3 U}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
4 X* I0 F4 \( A" ~( k+ Tnamespace 又费马达又费电
# R' G+ N7 J0 [- \+ E{
2 O% t  n/ I6 \: d1 P0 V    class Program
! ~& S2 M9 l  x    {9 i0 R) P& k; u, C
        static void Main(string[] args)
5 M( p/ Q( l4 f- a5 p, P# r0 h; R        {, V2 J# x( G/ N+ {/ w1 Z: ^" N
            int m, n;5 f7 Y7 I& R; z/ n1 q6 j, w1 W
            Console.WriteLine("请输入数组长度");! S% r, N3 b0 [+ n' }1 o
            m = int.Parse(Console.ReadLine());//m为数组的大小
6 ~9 d6 j/ L4 W" I! S' j            Console.WriteLine("请输入要截取数字的大小");
0 R$ ]# k1 G7 O7 w5 e            n = int.Parse(Console.ReadLine());$ z% D4 h3 v4 G# v
            int [] numw=new int
; B* m4 ?3 h' V9 |" L
: ]/ p' i7 u7 ]&shy;&shy;&shy;;
) r9 [0 w2 G+ y1 \            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数
( @4 j7 V% K( d1 ?" G            {
% G' H" T( c# Q                numw[j - 1] = j;
- @" w% ~- W5 q" k! Z- r" {            }
7 {8 ]  g. Y! Q/ \            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!
, v, ?* ?+ T  E  s8 j! J            while (d != m - 1)5 ^6 Z* f+ Z& t3 o' q4 M/ K2 |
            {
. ?- n5 y) t3 e0 A- l# U) b                if (i == m && d != m - 1)
- |  d/ _4 i$ \) W8 X- l4 p& I. }4 }                {2 c3 K( d) z* G, C
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!5 _+ {/ V8 T& K8 w! Z5 M; S) h
                    continue;& ^* @( ^- i$ r% G5 H8 i
                }. L5 r* _; t3 A4 i: X2 r( w" O' s% ]
                else# d+ @( s) R6 i8 d" W  K: g
                {
& G9 {% j6 O+ A: l                    if (numw[i] != 0)
8 L2 x" F! Z. r, S; x# \; I+ s                    {! S. K# F9 ?1 Y# D* n% B, U! T8 [8 [
                        i++;2 T' U/ H# R. J" x. v* y
                        k++;
5 X4 m5 {; o3 j1 Q2 s, |1 N                        if (k == n)
) z: R0 ]' s: D+ J3 e                        {
3 \  _5 `- C! T7 E; \4 {                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
! }! a  G6 g, }$ L                            k = 0;
6 U5 g$ V  C3 N" d- Z              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
+ R% u9 ^; I8 D7 D                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
- q+ n( g, I! E# B                        }: S1 J2 Y7 L; Y0 ?  i3 Z3 x  v5 n  P! }
                        else//输出暂时还没有改变数组元素的值/ `0 V/ U9 d( r. E4 R5 \
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
8 Q+ n0 ?6 B# w! L$ U( ]: r                    }9 P& L# {$ ~; w3 Q/ ]
                    else: i* p( Z: B5 K& x- ^5 N
                        i++;//数组元素为0,直接跳过,不计数。。。
& Z4 V% W$ E4 s, }+ h3 Z3 V                }4 J3 k9 q, X' k# i! ~  _  n
5 N, I  ^3 N. k
7 F9 A2 v" ?4 u& y" x* d
            }//结束while循环
( B; H$ c5 M! X/ I! N: L            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
# W  a. U+ S# h           0 `4 q( v1 A3 A# [6 H8 {
                if (numw[i] != 0)
' ]1 q' M- G; l+ l6 A. q                    Console.WriteLine(numw[i]);
( U' q1 r# C; p1 e8 \           : S( |6 U2 t; O5 ?" z' u2 G' x( O
            Console.ReadLine();% v% T/ `4 g; i1 k9 v; x
        }
$ @6 V% h# a7 P, t    }' I  s9 v4 ?7 N. C* V
}. k4 q8 C" l1 ~5 |* O) ^
小甲鱼最新课程 -> 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-3-27 22:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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