TA的每日心情 | 慵懒 2016-4-21 12:07 |
|---|
签到天数: 3 天 连续签到: 1 天 [LV.2]偶尔看看I 累计签到:3 天 连续签到:1 天
|
马上加入,结交更多好友,共享更多资料,让你轻松玩转电力研学社区!
您需要 登录 才可以下载或查看,没有账号?立即加入
×
郁闷 没人来给我加分!
3 h- p0 G6 x) D% G& D: X假设{1,2,3}表示1,2,3三个数的全排列,那么有下面的结果:2 g) n& n" i) v& `! w7 r1 d% T
{1,2,3}=1{2,3},2{1,3},3{1,2} 也就是说求1,2,3有全排列由三个部分组成了分别为1{2,3},2{1,3},3{1,2},大括号前面的称为前缀。一直递归下去就可求出结果。所以假设perm(int list[],int begin,int end)表示输出前缀为"list[0,begin]"后缀为"list[begin+1,end]的全排列"。
- d# {8 Q' W4 K0 D 令int list={1,2,3},所以:+ P2 A$ f# E; y( v* @; q( U# {
perm({1,2,3},0,2)=perm({1,2,3},1,2},perm({2,1,3},1,2},perm({3,2,1},1,3};6 o" [. G9 I- J# t
! `2 t1 t% ~: Z7 c1 F
3 N4 R1 N' Z5 A4 l0 z/ ?0 {- P 理解了这个式子之后就可以写代码了:C源码 #include <stdio.h>
2 F! {# X/ ~, M: t' l) h- A2 A, S0 x8 ytypedef int ElemType;
6 |7 d: l- c; h0 ?' B" `
9 m7 ^' s# Z! @% L: Y2 Q3 Fvoid swap(ElemType *a,ElemType *b){4 k2 s% x" F8 z! h
//交换2个数4 t- p8 Z2 r( F+ H& U5 ~
ElemType temp=*a;
r: |6 N" d- O$ S: ] *a=*b;5 m% Z" i$ b4 ?3 [& z2 _
*b=temp;
2 s/ i2 v+ h5 c( s7 N$ Q}//swap- K. U/ A9 q4 B# t& @0 D* N
+ {- m' s3 S% ^0 U! f$ U% _
void perm(ElemType list[],int begin,int end){( j* M R" a5 o' i4 U3 X
int i=0;# m- l0 f! Q+ m
if(begin==end){
" N% @, y: j- v) s for(i=0;i<=begin;i++)
' o6 C8 g4 j; Q: i0 _: Z3 \ printf("%d ",list);8 a( ^2 a/ M7 S( N
printf("\n");
. w) T: d( b, A: K% ]/ R* n }
8 k- g# t0 Q3 q2 n+ i7 `5 B else
% h" B+ ^6 t& j$ T; e* P$ C! ?for(i=begin;i<=end;i++){+ E- C/ I) Z- d# s
swap(&list,&list[begin]);
7 v4 ]' p3 U' ?* C o: w perm(list,begin+1,end);
1 M6 _% w1 d( k swap(&list,&list[begin]);
, |( p7 D# u6 ? x }
! D! G7 k5 S4 A+ X* P! A& |}//perm
5 I, i/ x* j6 n+ t. d" Q, Y8 {! _) C7 S% y
void main(){$ q" s0 U; x2 ]( e6 f% c0 f
ElemType list[]={1,2,3};
- w L; c9 G. O( Z1 U% f9 r2 P* X perm(list,0,2);3 e$ ~: [: ]; Z. s% f0 [
} : z( z3 h! F! K( }
0 D& |7 O" @2 g! }" F5 w& _+ R( K* Q8 Q
+ C( U5 d6 d$ i: g: \C++代码 #include <iostream>
1 o+ S- C9 w' l) r4 W4 M2 R b3 ]1 W& E" E
template <class _Ty>+ w& q8 d4 E+ u0 |, b1 e8 h9 b
void perm(_Ty list[],int begin,int end){
5 @+ s9 P" [- C2 ?' A; _ //输出前缀为"list[0..begin]"后缀为"list[begin+1..end]的全排列"---这名话很重要;
: s6 d7 |& e& |1 B //前缀是固定的,求后缀的时候要用递归求
) ?9 `( b1 X7 S( |5 r* q1 x) e0 b, @# ]
if(begin==end){
; o0 {, n/ N3 _# H2 j6 F& a //如果相等,则表明前缀为list[0..end],后缀就没有,所以直接输出前缀
: }- ?2 O/ R! [& T' x! E0 S& f) O2 \" ^
for(int i=0;i<=begin;i++)
9 S+ w% }3 P& U. M2 W$ i( ^- j std::cout<<list;; e$ }4 m3 \) S* ~4 W. y
std::cout<<std::endl;//输出一个之后,换行
* v1 h8 _& ?; p; m* G) M* Q }. `9 H+ y$ M$ j7 s3 W! z; a- O
else{
9 ^6 j0 v4 D/ Q& Y% t* E7 D' |* X //如果不相等,就要循环(end-begin)次,每次前缀都不同( J1 z: A( o1 V1 z# F
- \; W1 M# a3 m3 k% p* _
for(int i=begin;i<=end;i++){
4 D7 T8 q: c3 n6 d std::swap(list,list[begin]);//交换之后就可以得到前缀了
- `( ^" w, C4 L: s ]- L& k+ p/ w perm(list,begin+1,end);//递归输出4 L8 V* X* t! e1 G, x3 |4 u
std::swap(list,list[begin]);//换回来3 e0 x8 ]2 k# a
}# ` e h6 O: B5 v2 B- Z
}
2 u0 _- s! ? F& y}$ v. A0 s' g, ~% {3 S8 N o
3 f7 T; N3 Q0 z
void main(){. O: c$ b! S. W1 m
int list[]={1,2,3};) X& h8 j) s! w
perm(list,0,2);8 Z: H/ }" E2 c% ]) g
}
- H- [) E9 F* G4 E. c/ F' n1 ]0 r3 a9 O2 H! H
, f4 o: w1 z& `, H( y! J
C#源码 using System;
4 F7 w! L4 Z, c1 u; Z3 Rusing System.Collections.Generic;
+ j' t5 z1 Q' L1 }1 \* p6 d. a0 R- {+ m) Q2 ]
namespace CSharpDemo
5 ?4 ?# W& d- s) P1 e{6 ^" m, S9 W2 X9 Y0 I U |
class Program1 Y+ F& S% l! A) _% r$ D. \4 u
{" k3 N) R' |" T# E, r+ i- A
public0 {" J& a" n6 c3 k1 ~- s& P- _
static
% h; Z6 k+ K- W7 D) Mvoid Swap<T>(ref T a, ref T b)7 d7 V" d$ j, \" h2 y9 k
{$ G( B. B) z' v& r* Z8 G3 a: T
T temp = a;
5 P6 _. f+ Z% w! T# ~$ B- I, I a = b;
6 u8 A% m D4 m! w& z. G7 r b = a;
4 D+ K! D2 K2 i }; H, _# b" O2 e: N& I
; C) Z' h" T1 u% ^ V. K; ~! S. X; b+ O public. d- q) M: d8 N* F9 |& H
static( ]% {2 l: B: V2 u+ G" v7 w5 l
void Perm<T>(T[] list, int begin, int end)3 Z/ T0 L6 w" |5 V
{
2 V. r; D# R! P& {) [/ m; d if (begin == end)
! I% b4 r% ^& g7 a) J: v% \1 ~, N {
5 A% a4 \9 p) q# h for (int i =
0 K1 V* V6 I, m; A0; i <= begin; i++). n* g0 x6 U4 }: a# z! g
Console.Write(list);) R0 r& K g- I$ d! T
Console.WriteLine();- K: H9 `5 \( @# R
}
' ^4 z. i( [$ P) i; e else
3 j ^% P: \# U$ _for (int i = begin; i <= end; i++)
; H- V( V1 F" J6 o {6 b& X4 [" G4 F. f) A% h+ G
Swap<T>(ref list, ref list[begin]);
$ W8 P0 A* _3 u$ d$ V; P Perm<T>(list, begin+1, end);
4 j3 g2 f* @( |. R! N Swap<T>(ref list, ref list[begin]);
/ F& Y8 y+ W! N" A: q( B( \( U }, X. n7 u$ n0 S0 f. A5 R! ]
}9 j8 h7 f; X+ V; V6 j
0 ] a. b2 F0 n* _/ v static1 Q7 n8 H, |, o
void Main(string[] args)
& a7 @$ v A. b: k/ n0 ]# G {
T; J8 x* ~: o: L int[] list ={ 1, 2, 3 };& T6 \2 d: j8 H/ b8 T
Perm<int>(list, 0, 2);
/ {" X; H' J- A* r }
1 B+ E* g; Q% Q& C: M, i. @ }" S- X" T- ]4 v1 V3 _
}
: ]2 K0 B9 H+ M3 Y |
评分
-
查看全部评分
|