鱼C论坛

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

猴子问题

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

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

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

x
大家好!* U0 X8 f3 I' v9 Q8 L$ F% d
这几天我在忙着编一个问题,我用了一种方法编出来!' b( X, h  g: Y! s1 O# T0 V  W  R
但是当我编完时我去看书! 发现许多的方法 我看了看,拿出来与大家共享!还有附件哦!+ W/ L8 W' ~" x& V
注意拉!第一个是我的原创哦!!!!! 如果有什么不对的地方请大家指点出来,本人不胜感激
# d$ _" [6 f/ L! d4 [' f0 d5 C/ I; q* S  ^: j
8 k0 ~0 N) W. q) |( _  {
                            题目0 q% u/ `& H; ]
山上有m只猴子要选大王,选举办法如下:所有猴子从1到m进行编号并围坐一圈,从第一号开始按顺序1,2,...n继续报数,凡是报n号的猴子都退出到圈外,照此循环报数,直到圈内只剩下一只猴子时,这只猴子就是大王.输出大王的编号。
7 h/ m. V6 {8 k/ v3 n3 ^3 W7 |/ Z" _1 k7 C第一种方法:利用循环链表
0 |: ?7 r3 u4 _9 X3 A#include<stdio.h>3 c9 ^9 e0 B5 Z, B. c# p. V
#include<malloc.h>8 }( b/ X0 I7 _- K, `
#define M 8            //共有8只猴子
5 k  z$ c8 `& n, ?# x#define N 3            //数到3只时退出第三只
2 [1 E2 G8 C' n- O1 Z4 M- K3 B3 otypedef struct monkey& |0 H1 I5 i/ Z
{int number;; J% s6 M, p+ M- ^9 i
int flag;
9 T) z% V4 |) U) O/ I2 a6 hstruct monkey* next;: q' T3 v6 ]/ ~
}MONKEY;) B& D8 O2 ~/ z2 i9 h
main()$ q; ]: Z' ^' f0 D% g1 W8 S
{ MONKEY *head=NULL,*p,*s;; k9 F5 D. G0 l- z# G$ C1 c
  int i,sum=0,count=0;% h; F, {' X7 B7 ]7 K. ~, Y
  clrscr();              //清屏2 Q0 j# H& x8 E# z. h, }; K
  p=(MONKEY *)malloc(sizeof(MONKEY));  //分配内存
) I+ t4 b8 @0 J* ?7 Q8 |: n  p->number=1;p->flag=1;3 `8 p+ m$ Z0 t' L$ b
  p->next=head;# ^* m0 H% q- o6 s; }* x" u
  head=p;8 R5 z1 b  P+ W8 [+ P
  for(i=2;i<=M;i++); E- q- }; z" H, _
    { s=(MONKEY *)malloc(sizeof(MONKEY));0 {0 c0 h# y0 m" T) T
     s->number=i;s->flag=1;: _5 N) n( U4 M( ~! @- m
     s->next=head;3 _  k1 |3 c! I" ^2 o
     p->next=s;p=p->next;6 z- l$ \+ `; [! @7 @
    }' W( w" ]  n/ I: G( o- O- c
    p=head;5 D- N7 B3 _! q' H+ `/ f4 ]
   for(;;)
1 p- O5 _' X$ o1 i  l4 X    {if(p->flag==1), C7 H1 O$ \, q$ H9 [# ^
       count++;
7 D0 i; ]! [: P4 _7 s7 z5 W     if(count==N)
& _* l% X% k+ m$ ]- ~* i, h8 O        {p->flag=0;' I5 b3 N0 V# L$ l3 _6 _% |
         count=0;
8 z! @5 I# n2 k$ z0 H* U         sum++;}
8 i5 s3 m* m* ~& x5 O# X! t& O# }     if(sum==M-1)* d8 ^, G" y8 ~1 V, o7 w
        break;
4 B  P& A+ d* N: G     p=p->next;- |" N! x+ `) o, d) r( q, C) S( B" x
    }6 d* I" N! @) L$ d9 M; Z
    p=
( o: n9 @3 \. e8 M' w0 Z    head;0 F: j+ ]; y: o6 f% H9 [2 R0 U
    for(i=1;i<=M;i++). k& M2 N; [# E- L2 _+ A( `+ I
    { if(p->flag==1)
( {1 ~1 v, L% Z3 ~$ k        printf("\t%d",p->number);
- I! o6 n5 R! L2 `- W) K      p=p->next;3 X+ a% a0 k3 X* u
    }  I6 V; m; V, J( |  y" N- @9 [

1 U5 G6 q5 q5 U$ K- `+ d9 _/ u( k8 Z7 I" O. _; x
$ _0 d) g* S, p. o* d
}
  ?7 ^4 ?3 }* i
第二种方法:数组4 r3 u9 P6 R' h0 j
#include<stdio.h>
4 N2 Z/ P$ V4 X/ W  |3 m4 F$ o#define M 81 O  L& g6 z/ E: }6 [& @+ V
struct monkey# N, m* U0 i- k' Y2 }- `( ~% J
{int number;7 l7 P5 U% L) x2 p+ H% q
int nextp;
9 b  S7 g0 l% l1 W2 N) J}link[M+1];" {; p2 |/ n1 t8 a% _

- B9 j  ^; C; evoid main()
: [2 E  S6 m* L; `2 o, F{int i,count,h;
" |3 A" z) T/ f8 o6 {8 C* X0 Afor(i=1;i<=M;i++)
( i% e6 U% k& h0 C- j7 |" m% K{  if(i==M)
) B3 v; C0 M; h1 E- h. s# h   link[i].nextp=1;
9 |4 q- h8 }/ V5 w- A   else
! t/ T/ e% [7 Z% m- E: ~8 v   link[i].nextp=i+1;
& x0 w. |7 e0 v: J  link[i].number=i;/ `$ \2 S# U8 i1 M5 a9 D, U0 n" ?
}4 B2 c+ O% W5 Q) p( K% d1 L8 i3 V0 J& h
printf("\n");
2 U6 t; @3 k. y# g1 J& h& Xcount=0;! A/ A* S, V+ q
h=M;; F* Z4 K# m0 x$ _
printf("依次退出的猴子: \n");: U6 ]! D$ a  \. C* |  I3 a
while(count<M-1)
# q& I: y+ J$ O% w! k2 b' V{i=0;" x7 _( y0 e0 r" {
while(i!=3)
- _% O, _8 F9 Z' t# \+ S$ {{ h=link[h].nextp;0 \" _( Z% s6 s4 {4 O4 @
   if(link[h].number)( g: j: Y1 E: S1 K) L6 B+ }
     i++;}, i+ w) G7 A4 A) d
/ B# G1 L3 L( n1 _
printf("%4d",link[h].number);
3 g2 b# I% n4 P- k& ?- ^7 @link[h].number=0;
8 b: _' E6 H  ]3 E1 `) Ocount++;7 t: t( L+ l4 n4 m8 Z8 O# m
}" r$ h; k% A0 B, f" ^7 t! m

+ v" G( o9 n! d8 sprintf("\n大王是:");  F/ j8 k% t+ X, z* K. L
  for(i=1;i<=M;i++)- T$ h! v; `" t! Y3 Z( I
  if(link[i].number)
2 S* q) P; q9 \2 d    printf("%3d\n",link[i].number);
* `( ^7 C# J" o! j& J9 Y# x3 b  c  R
; E, l% B9 M7 k7 B+ q( g
}
9 j$ B$ T0 k4 a; S% I
第三种是普通方法for循环

, Z5 v$ C! ]7 j" a& \* X! s' p0 z#include<stdio.h>6 h0 I" W$ `9 r* H" P: P
void main()
! `0 D+ W( b' W( ?8 o; X{ int i,k,m,n,num[50],q,*p;
6 S6 ]1 G% p; \5 Z8 q' u; k8 `    clrscr();
  o; X. ]' b0 R, a) i0 a9 y% ]   printf("input number of person: n=");* s1 f2 h( e. q8 X7 d) B
    scanf("%d",&n);
0 ]6 \+ M7 X5 h" ?! A% F" d5 T5 bprintf("\ninput number of person when how many monkey exit: q="); //输入数到q只时退出第三只* k1 s9 L3 \' a9 x$ k+ k
    scanf("%d",&q);/ G) e* M: E7 [% u& F
   p=num;/ O7 x& \% p9 D" e, `
  for(i=0;i<n;i++)9 f0 s; A' \8 L
    *(p+i)=i+1;$ X1 @; _/ ?2 W$ j5 D
   i=0;
" n6 f9 B1 g3 {: G; F7 m8 e/ p   k=0;& F3 ^' B8 \6 T1 s8 j
   m=0;
+ G  n) A, I/ ]- k. t  while(m<n-1)
* z& p# H8 T$ ?& Q- b- U+ v! `8 F   {if(*(p+i)!=0) k++;
4 C! A9 O; \# j- F     if(k==q)
' m0 j8 U: Q  {) T  P( H* L      { *(p+i)=0;$ H5 s4 [! q2 K! ?: |# q; {  m
        k=0;
" k& [* L7 R  k" y        m++;
# f- c' A' v. e1 |. Y      }
& r. z; b# c- G  t8 _    i++;% R$ w' P7 [9 W& W( [
    if(i==n)i=0;/ J+ v! O' V. T- B' B/ s
   }% N" E; {2 ]2 K
  while(*p==0)p++;1 [/ w2 k' z- {0 m, n. R9 V
    printf("The last one is NO:%d\n",*p);( K) r1 ^) t' S0 T  I
     getch();; P) I5 c2 }+ J" b, m

2 ^. r- S6 u) v4 D+ A  W}
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:28:46 | 显示全部楼层
{:1_1:}这个题以前读大学的时候做过!我是用C#语言写的!待会儿拿出来共享
小甲鱼最新课程 -> https://ilovefishc.com
发表于 2011-10-24 17:32:28 | 显示全部楼层
using System;2 S8 I( z' W$ }9 E' _& N3 j# g
namespace 又费马达又费电
  s1 r5 b0 n( @( B4 M! L{  C! j. G; Q0 ]/ Z* r1 g( I" C
    class Program) H+ a$ a7 @: k! F$ g3 C! ]# m; y
    {) Z# G+ D3 K; j6 A* Z
        static void Main(string[] args)- R- j$ S# I* I1 I( g0 s2 p- G1 \
        {
7 ]4 \+ c( E6 F9 D3 q% w9 Q            int m, n;
3 u" B1 L8 Y/ k. ?- ~& \            Console.WriteLine("请输入数组长度");
3 U" A! V- v, C# \0 u$ B            m = int.Parse(Console.ReadLine());//m为数组的大小
: @( A+ }' {* ]2 T4 R            Console.WriteLine("请输入要截取数字的大小");( ^- K) G4 }8 T; K% R
            n = int.Parse(Console.ReadLine());3 p! t' A& k2 |0 d* L
            int [] numw=new int+ y7 e; }3 R8 v* h7 B

+ T: c0 F2 y& F& C1 |4 t' h&shy;&shy;&shy;;; `. y$ A# M. Q
            for (int j = 1; j <= m; j++)//给数组赋值1开始的整数+ x+ _- H/ W6 Y2 b. Q$ }
            {
% E( s! I. ]8 \! ?                numw[j - 1] = j;
  [$ N! q$ ]: o5 R            }% h! h$ R- v& k, q- A
            int i = 0, k = 0, d = 0;//声明一组变量给while使用哈!!+ t* w+ C, f7 a1 j. @; M
            while (d != m - 1)$ R8 }# r: n7 A# |2 E
            {
0 I1 Y9 q* E  {# W/ V5 g8 F                if (i == m && d != m - 1)  T' {# C+ T4 z* q0 K1 y0 P4 j# m
                {; `  X: ^6 B: M7 |# q9 ~
                  i = 0;//i控制每次遍历数组的变量,用它一次次遍历数组的啊!!
3 S( B( i7 j4 h; x4 C( h* A( l                    continue;
/ u8 b0 [7 P- W7 R. M6 P                }
5 w9 K% ~9 w4 @. N- I) X6 j. S                else( h3 F$ J1 }$ V4 q+ {1 G  F
                {7 I- k1 w' ~9 c0 P* n4 o2 a" {, \
                    if (numw[i] != 0)8 l6 M/ f$ w  e, H1 V' \: c3 z
                    {
+ ^7 I5 v0 }: J$ @                        i++;
9 z2 l+ L5 F8 F  w/ Z$ S& P                        k++;
* }+ `% l! s4 [' G+ ?3 ~2 ~/ v1 L, Z                        if (k == n)* A6 I) Z0 b+ J- `* _" s" [
                        {
4 y! k# X3 Z% g, n6 k                            numw[i - 1] = 0;//把在n位置数组元素的值改变了
# a2 |" e+ X( L7 q- C, ?- {                            k = 0;
# X7 M0 H% [( E4 g1 C              d++;//每改变一次数组中元素的值,d就自动加1,但要比数组的长度小18 m/ {" }# L0 x% ^) C
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);
. K3 c7 f5 ]9 M' s                        }
+ ~8 g% L& A* x  H4 B% f                        else//输出暂时还没有改变数组元素的值8 D/ J* y" N; ~
                      Console.WriteLine("numw[{0}]={1}", i - 1, numw[i - 1]);& _$ M: j' N& E' i' B) H
                    }
7 P' @7 Q2 y: U  D2 [                    else
2 x. L& B. q' a( Z                        i++;//数组元素为0,直接跳过,不计数。。。
  z; T6 L, o9 o9 w$ D/ f7 r" [                }9 I# `0 H& x# Y8 I+ D" |6 E! p
* }) [. x( F0 @  F4 F1 Q

4 z1 l9 C) A6 P            }//结束while循环3 \2 }( R; D) w4 i  u
            for (i = 0; i < m; i++)//输出剩下那个数字,得到最终结果了哦
7 `4 a2 ^: A8 i: J           
6 W: u7 W# \2 m0 i" M  d0 f+ W                if (numw[i] != 0)
* F" e3 V* A5 V6 Z# a8 Y. _                    Console.WriteLine(numw[i]);
& d# |- }& b3 D- g$ u1 y8 r           
% a- z7 p7 \/ h8 F            Console.ReadLine();8 x/ Y8 V  R7 f/ v+ b6 D
        }: e& b  A+ {1 E2 M7 ?
    }) L/ k* B5 P2 \$ j
}7 ]* l* ^8 O  |; 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-3-7 23:19

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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