鱼C论坛

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

猴子问题

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

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

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

x
大家好!, K) x. R: h* |5 ~9 ~* _! X( T$ e
这几天我在忙着编一个问题,我用了一种方法编出来!! q: z  r. k5 U- m
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!
( b: |: J$ r5 [注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
# x, i) ~. M* K; W$ u0 U, z% e" s7 V) C/ f3 t6 M9 l$ |, j3 f
0 F5 s) ]3 q  ~! Z0 R/ V
                            题目
) ^  T4 L4 E3 g$ g, \) W3 [( h山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
& G0 R( o5 w. }0 I  x" K' D第一种方法:利用循环链表4 ^0 h" t: M1 l- `: M5 N
#include<stdio.h>) m1 Y( ?3 \+ n, w- z% O0 ~' O2 A
#include<malloc.h>
2 u' E+ ]; M! R3 j' e#define M 8            //共有8只猴子
+ [8 [9 U* _( Q0 Z; l#define N 3            //数到3只时退出第三只5 i  x1 Y2 ~' @3 M
typedef struct monkey
& o5 v$ ?2 _! d! y$ O6 J{int number;
" m, g0 w/ H2 A: rint flag;. L) r9 M8 ^1 L* M
struct monkey* next;* l& S9 d3 |7 `: r' d6 D
}MONKEY;
2 z% T7 _  b$ w' wmain()
* {3 p+ W  Z/ ]* V- z: H{ MONKEY *head=NULL,*p,*s;
% O9 ]5 c! G6 L  int i,sum=0,count=0;- R5 h& |  W, Q' y$ C
  clrscr();              //清屏
3 M' m% J& A/ k7 f/ H$ z" T* r7 y  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
2 W9 r7 }2 r! O( B, Q2 G' ]  p->number=1;p->flag=1;
6 _6 j: w' A5 H+ x  p->next=head;
" m# ]. P" N9 o' k) M  head=p;
" U& S6 g! a7 \. e4 i2 y- k! J  for(i=2;i<=M;i++)
+ w( o; z- X. ^  d- A4 F4 u    { s=(MONKEY *)malloc(sizeof(MONKEY));6 U8 p* v  ~$ T  H  `  r% \
     s->number=i;s->flag=1;
; N  K: B3 y8 A: ~     s->next=head;6 Z1 v/ v$ v4 v7 a& q4 _2 x
     p->next=s;p=p->next;
( v/ K3 Q6 H0 O" Q! J$ n    }5 q- G# I( }& }% @
    p=head;( T8 ?5 ?+ s1 D+ W5 S8 y
   for(;;)
. X. i3 J. A8 e2 ~/ a; }3 _    {if(p->flag==1)
2 r9 i6 T, q/ F$ e& \       count++;
- R8 `7 q$ [7 ]& n# u     if(count==N)7 F; I5 |" M. F. `) K2 K" c
        {p->flag=0;
+ g8 _9 V% X% ^; q0 u/ H* v         count=0;* {" d3 j9 _9 }: E
         sum++;}
9 A5 J; ~: `9 w+ _' Z1 C. p     if(sum==M-1)# z* Y# b( H4 m. }
        break;
) T% [' S  m! s& @     p=p->next;. G4 u8 }+ P6 d4 q4 D5 B6 q
    }
* F# B9 E0 k, @5 g    p=
  C1 Q# n8 I) R    head;( O! p4 u  N+ M* b- X
    for(i=1;i<=M;i++)
' V3 p; A% n# f4 R$ Y    { if(p->flag==1)2 n6 p+ p: T; t6 C+ B
        printf("\t%d",p->number);
, \1 ^9 c+ C% r- x# J! j8 X+ L      p=p->next;
. q6 d* q1 V$ d$ x( A+ E0 S1 c, T    }1 e$ x) I& |9 a1 K8 y1 i5 U/ f
" w9 i* |- Y5 }
' h9 L, y4 w) J' u

0 C  {: I1 S3 z}
% B. t2 E2 t/ w
第二种方法:数组1 A: o& {: |' @; c6 @. q
#include<stdio.h>9 P! v3 q4 A+ C# F9 ^
#define M 8
; ]6 P0 n4 p+ P. g8 ^" k7 x4 lstruct monkey
- [& W' G3 f. A" Z{int number;
$ _0 w( m8 c) p0 m6 s7 zint nextp;
! q! V! e: b* ]! n! Q}link[M+1];$ G, V3 K7 O# Y% a  d6 {
( F( x1 q2 I% s0 R
void main()  y% R( V3 L- f0 S: s' z
{int i,count,h;
2 ~! }2 |* N- M4 t) Efor(i=1;i<=M;i++)
# o" b) G; s5 e& e& Z3 ?{  if(i==M)& o, z9 l$ K7 j' {0 u* p  P, F; I0 o
   link[i].nextp=1;
$ u' W0 B, V* x$ c6 X" F/ g   else+ m$ ?8 q% s+ n
   link[i].nextp=i+1;
6 u5 Z% d0 M2 e0 {$ P$ Z  link[i].number=i;
  o" Z$ I. S0 z3 U: d5 W}
# S( V! U' s6 L# K- W" T6 Cprintf("\n");
6 F1 L7 I! D0 g& M: e& |count=0;
- v5 x+ j+ c& p( r# ^h=M;5 Q$ B7 B( r$ x4 P) Q" b% b
printf("依次退出的猴子: \n");
+ Z3 z- n# m! V9 Dwhile(count<M-1)3 k5 G) u! d& d0 t+ v+ D
{i=0;
* C. B2 x; T% O1 Mwhile(i!=3)7 ?0 Z6 G& H* |+ F  d: v, t
{ h=link[h].nextp;: G  d1 f/ v# N. h
   if(link[h].number)
1 B  y" [0 V# X' K1 q( {' p0 E8 y     i++;}
* G  _! d) R' z! A! s% ?$ z# O( ~; I
printf("%4d",link[h].number);8 b; l( T& D* S/ L. s  n1 {8 A$ f* ?, \( x
link[h].number=0;& r5 {) W* H$ h- M
count++;
$ p9 D, L8 v! s}  y1 J9 T  {6 ~5 ?. r# ^1 t( D; [3 E* S

0 F; n, c/ f7 {  }+ ?printf("\n大王是:");! W+ F5 I. q6 e
  for(i=1;i<=M;i++)
) Q# v  M" X0 S; U) c8 o$ Q$ M4 U  if(link[i].number)# k1 T* _% l- V8 f& K7 D
    printf("%3d\n",link[i].number);& @8 ?* {6 i; |+ c
& X0 f( d; y  |. W+ c) ^5 G

8 K; J2 J0 x# @" Q6 F}

: C: ^4 Q1 R/ F7 m7 B. u9 G第三种是普通方法for循环
& I6 [( \) @/ Y% Z; l" ^
#include<stdio.h>
7 S6 \5 Y6 Y3 s7 p8 p" C  A% Q; L, Bvoid main()
5 ]+ R6 |7 n( h+ F; g  u) h{ int i,k,m,n,num[50],q,*p;
' \3 |" ^0 t6 q" t3 ^8 |) l; t    clrscr();
9 i4 ~5 U3 @; p) z7 W% P   printf("input number of person: n=");
. H3 f. j/ Q+ j8 O6 Y% _: N    scanf("%d",&n);
, ~% y3 [  w/ V" Jprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只
; G8 k/ p5 N! L# B/ u6 {; p2 v    scanf("%d",&q);1 J) ~; w( V9 n3 ^
   p=num;( r: a7 N# `/ u' {0 I1 e3 r; f/ g  o! g
  for(i=0;i<n;i++)' r  c; x: c9 y) c/ f- z9 K2 s* o
    *(p+i)=i+1;4 D: _1 Q& [% X
   i=0;# G/ e% O9 j; }/ \+ `: x
   k=0;# y! o) [9 F) z9 f# T, c
   m=0;3 V. k. I. K/ N1 `- P. c
  while(m<n-1)
+ p6 y* g. ]" Q5 W7 M6 A2 ?! {& I   {if(*(p+i)!=0) k++;
' [2 D0 E" t- c6 _1 P1 D+ N# G     if(k==q), A9 x4 }" h! `4 O2 u# R
      { *(p+i)=0;) M& V) n! _* k5 |  k
        k=0;5 L5 Q3 B; F' s8 d4 F! {
        m++;$ s+ k7 B  M& g" ?5 P, T3 W
      }1 I7 i) K% ?/ i
    i++;( f# |: H6 G& n& }* i0 R
    if(i==n)i=0;* u; l6 X" \- R. s( L. W7 U
   }4 p2 }& ]: p2 r1 g  Z/ I# h" U3 n
  while(*p==0)p++;
- T3 ~& T: _, B! g& p) R% Y3 b! Q    printf("The last one is NO:%d\n",*p);8 U! x* C$ J! |* R2 c- o0 U
     getch();9 k1 Z! X+ A. |

6 e) p- A2 D7 ?' g4 R9 N6 r7 W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;
3 a) M9 C2 s: Ynamespace 又费马达又费电
( u; Y6 \; N) _5 b) c{
/ b  ~. z" I1 i2 _! T4 A    class Program
; ^0 Q' j5 Y% d6 @- q    {, w9 ]; N& l) i' q+ x( r5 c) J
        static void Main(string[] args), z2 P: Y* r5 x$ |" D" F
        {( D! T- n4 o8 \; @0 I' g' h, Y
            int m, n;
5 n% T" r2 X& |9 q. p, x" X" E- X            Console.WriteLine("请输入数组长度");
# y' s9 q8 L2 q3 |9 u            m = int.Parse(Console.ReadLine());//m为数组的大小
, b. L4 V( Z: ?/ D3 T$ _) V% P% O            Console.WriteLine("请输入要截取数字的大小");. b2 x+ m  g/ I4 R3 J& g9 ^9 ]
            n = int.Parse(Console.ReadLine());) L8 e  r* m' @* B6 h
            int [] numw=new int/ m# S2 M6 n1 s7 U/ e3 j* @
/ k, n7 x/ B' o2 W6 X2 T
&shy;&shy;&shy;;
5 c2 V7 [' x, R! x            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数1 G! x- C5 P. {
            {
/ T& n: a$ n. R+ H                numw[j - 1] = j;
' \0 ]- U+ w% k. A            }$ n; C: b9 @5 b! ^- I
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!! g  a% X, ?. t0 W# C( c
            while (d != m - 1)
- q* q, \9 K8 @1 {+ v* ?            {
8 b+ P  l' h* d5 O6 d% v                if (i == m && d != m - 1)2 V3 x5 r: y' d0 W& `. `  g0 W
                {+ `0 E* i; Y0 g
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
. M, O8 Z! T& t7 q! G, g                    continue;
1 o7 ~$ y( Z9 Q% e- t0 D) R% Z1 }' N                }
+ ?4 M  Z' `% _6 ]                else+ z* V; u# h' Y! v# B
                {
- Y$ R4 x2 w: ?. I0 _                    if (numw[i] != 0)
$ ^3 a! a/ n" [: M8 e; z  o                    {
, j, C5 j7 n1 b; h' T4 h' b" {                        i++;
- c3 Y, ]7 h' w, G- W                        k++;
; `3 N5 @8 }0 R                        if (k == n)( x' c( B5 F- G2 B  b( U
                        {
9 X. M+ e, d( Q" k9 H                            numw[i - 1] = 0;//把在n位置数组元素的值改变了* Q  h; M; Z9 F4 t; E
                            k = 0;4 F- l5 L; y5 Y) y& ]8 ^( X! {
              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小1
1 U, T8 @/ }3 Q3 J* G2 ^                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
$ z& [4 }( g$ }1 T  Z7 U; S" A                        }
: @$ s# `' g! b                        else//输出暂时还没有改变数组元素的值3 x7 E$ m0 O4 @- j2 @6 X
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);2 g2 P6 F% p8 }
                    }
1 K  `3 @  m9 q. @# z9 l                    else( A9 ^& m( d% d
                        i++;//数组元素为0,直接跳过,不计数。。。: G4 {% J9 `; c  h( ~( |" e; n
                }
) ~+ g0 f  u) E; M
4 n4 k5 ~0 v# b" N" N% {2 f% i) y* b+ \7 Z+ Y
            }//结束while循环: s! C% ^" ]7 Y' |
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦4 C" l9 G, d4 \
           
) T$ f9 j" [) {9 L. r5 ~% x. m" S                if (numw[i] != 0)
! B0 K: b9 P! S) ~                    Console.WriteLine(numw[i]);" [% P5 R( w( d: _- W
           4 U0 i- [  x$ y! J; e
            Console.ReadLine();; }6 ]8 _! W: e$ S: ?5 J, d
        }
( i& B% M& `% X- [1 x4 [9 i    }9 E: R$ j6 y" k3 P, s1 b
}
6 \7 j5 h& ^$ v7 Z. \
小甲鱼最新课程 -> 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-18 22:12

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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