알고리즘 질문 - 0~4까지 중복없이 찍어보자
글쓴이: koku_ma / 작성시간: 목, 2007/09/06 - 2:54오후
0 1 2 3 4 이렇게 5개의 숫자가 있습니다.
이걸 아래의 형식과 같이 중복없이 전부 찍어보고 싶은데 잘 안되네요...
아래와 같은 형식으로 찍을 수 있는 알고리즘을 좀 알려주세요.
0
1
2
3
4
01
02
03
04
05
10
11
12
13
14
20
21
22
23
24
30
31
32
33
34
40
41
42
43
44
001
002
003
004
005
010
011
012
013
014
020
021
022
023
024
030
031
032
033
034
040
041
042
043
044
101
102
103
104
이런식으로 해서
끝은
44402
44403
44404
44405
44410
44411
44412
44413
44414
44420
44421
44422
44423
44424
44430
44431
44432
44433
44434
44440
44441
44442
44443
44444
이런식으로 ....
고수님들 부탁드립니다.
Forums:
진법 변환처럼 생각하면 쉽지 않을까요
속도가 중요하지 않다면(...)
단순히 저걸 5진법으로 보고, 0~44444(=십진법 3124)까지 변수하나를 증가시키면서
5진법으로 변환하고 찍어주면 되지 않을까요
제가 이해한 게 맞는지 모르겠지만...
BackTracking을 사용하면 다음과 같이 짜볼 수 있네요.
public class PrintNums { char[] numA = {'0', '1', '2', '3', '4'}; char[] memA = new char[numA.length+1]; public void print(int totalDigits) { BackTracking(0, totalDigits); } private void BackTracking(int ix, int depth) { if (ix == depth) { for (int i=1; i<=ix; i++) System.out.print(memA[i]); System.out.println(); } else { for (int j=0; j < numA.length; j++) { memA[ix+1] = numA[j]; BackTracking(ix+1, depth); } } } }위에서 totalDigits수를 변경하면 원하시는 자릿수가 나옵니다.
하지만, 이 방법은 자릿수가 커지면 무척 느려지죠..-_-a
(다른 분이 더 우아한 방법을 알려주실거라..)
ps. 안타깝게 잘 쓰지도 못하는 자바로 짤 수 밖에 없는 환경에서...
토나오게...
이렇게 하는 법도...
루프가 이중이라 별로 효율적이지는 않지만, 이런 방법도 있어요.
void print(const int width) { const char num[] = {'0','1','2','3','4'}; const int size=sizeof(num); char a[width+1]; memset(a,'0',width); a[width]='\0'; while (1) { int i; printf("%s\n",a); for (i=width-1; i>=0; i--) { (a[i])++; if (a[i] == (num[size-1]+1)) a[i] = '0'; else break; } if (i<0) break; } }begin{signature}
THIS IS SPARTA!!!!!n.
end{signature}
댓글 달기