1. 느낀점 및 설명 ¶
일단 만들기는 했지만.. 조건을 만족시키지 못한다.
나름대로 줄이긴 했지만.. 애초에 문제가 나빳던 거얏!!ㅠ.ㅜ
두개를 곱해서 21이하라는 조건인데.. 최악의 경우는 각각 3개의 뿌리를 가질때 깊이가 7이되면..
3280개의 노드가 생긴다. 고로 이걸 3280!해서 나오는 경우의 수를 생각하면 10^10000이 사뿐히 넘어간다는... 애초에 계산이 될리가 없잖..
일단 임시로 만든 소스를 올렸다. 현재 연산에서는 문제가 없으나 3*2를 넘어가면 연산속도가 눈에띄게 저하된다.
물런 나름대로 머리를 굴려서 계산양을 줄인건데.. 조속한 시일내에 해결책을 구상해서 수정하도록 하겠다.^^*
역시 또 머리를 굴려서.. 하단부 속도 개선~!!
21*1이라도 빠른 속도로 계산하지만.. 깊이가 깊어지는 경우에 대해선 아직 약하다..ㅠ.ㅜ
어떻게 해야 하려나@@
아..그리고 그 결과값을 넣을 만한 변수도 없.. 너무 크잖아..;;
2차 속도 수정..
이제는 5*2라도 풀 수 있다. 저번 펙토리얼식 알고리즘을 조합식 알고리즘으로 수정하여 많은 속도의 향상을 가져왔다. 하지만 모든 결과를 내기에는 충분하지 않은속도..
아아.. 이이상은 쪼금 버거울 듯..ㅎ
2.1. VER.1 ¶
~cpp
#include <stdio.h>
#include <iostream>
struct block{
int number;
int deep;
int maximum;
block* head;
block** next;
};
int get_number_nodes(int , int);
void change(int*,int*);
block* create_block(int, int, int, int, block**, block*);
void process_block(int* , int , int , int , int , block** );
void main()
{
int degree, deep, number_nodes, answer_number;
block** line;
printf("트리의 분기계수를 입력하세요.n>>");
scanf("%d",°ree);
printf("트리의 깊이를 입력하세요.n>>");
scanf("%d",&deep);
++deep;
number_nodes=get_number_nodes(degree,deep);
line=(block**)malloc(sizeof(block*)*number_nodes);
create_block(0, 1, deep, degree, line, NULL);
process_block(&answer_number, 0, number_nodes, degree, deep, line);
printf("결과 : %dn",answer_number);
for (register int i=0; i<number_nodes; ++i)
{
free(line[i]->next);
free(line[i]);
}
free(line);
}
int get_number_nodes(int degree, int deep)
{
if (1==degree)
return deep;
int temp=1;
for (register int i=0; i<deep; ++i)
temp*=degree;
return (temp-1)/(degree-1);
}
void change(int* number_a,int* number_b)
{
int temp=*number_a;
*number_a=*number_b;
*number_b=temp;
}
block* create_block(int input_number, int input_deep, int input_all_deep, int input_degree, block** line, block* input_head)
{
block* temp_block=(block*)malloc(sizeof(block));
line[input_number]=temp_block;
temp_block->number=input_number+1;
temp_block->deep=input_deep;
temp_block->head=input_head;
temp_block->maximum=get_number_nodes(input_degree, input_all_deep)-input_degree*(get_number_nodes(input_degree, input_all_deep-input_deep));
temp_block->next=(block**)malloc(sizeof(block*)*input_degree);
if (input_deep!=input_all_deep)
{
for (register int i=0; i<input_degree; ++i)
temp_block->next[i]=create_block(i+get_number_nodes(input_degree, input_deep)+input_degree*(input_number-get_number_nodes(input_degree, input_deep-1)),input_deep+1,input_all_deep,input_degree, line, temp_block);
}
return temp_block;
}
void process_block(int* number, int block_number, int max_nodes, int input_degree, int input_deep, block** line)
{
block* temp_block=line[block_number];
if (block_number==max_nodes-1&&!((temp_block->head!=NULL&&temp_block->head->number>temp_block->number)||temp_block->number>temp_block->maximum))
++(*number);
else
{
for (register int i=block_number; i<max_nodes; ++i)
{
change(&temp_block->number,&line[i]->number);
if (!((temp_block->head!=NULL&&temp_block->head->number>temp_block->number)||temp_block->number>temp_block->maximum))
process_block(number, block_number+1, max_nodes, input_degree, input_deep, line);
change(&temp_block->number,&line[i]->number);
}
}
}
2.2. VER.3 ¶
~cpp
#include <stdio.h>
#include <iostream>
struct block{
int default_number;
int number;
int deep;
int maximum;
block* head;
block** next;
};
int get_number_nodes(int , int);
void change(int*,int*);
block* create_block(int, int, block*);
void prv_process_block(int);
void plus_process();
int Get_combination(int, int);
void Block_move_process(int*, int);
int degree, deep, number_nodes;
unsigned _int64 answer_number;
block** line;
void main()
{
printf("트리의 분기계수를 입력하세요.\n>>");
scanf("%d",°ree);
printf("트리의 깊이를 입력하세요.\n>>");
scanf("%d",&deep);
++deep;
number_nodes=get_number_nodes(degree,deep);
line=(block**)malloc(sizeof(block*)*number_nodes);
create_block(0, 1, NULL);
prv_process_block( 0 );
printf("결과 : %u\n",answer_number);
for (register int i=0; i<number_nodes; ++i)
{
free(line[i]->next);
free(line[i]);
}
free(line);
}
int get_number_nodes(int degree, int deep)
{
if (1==degree)
return deep;
int temp=1;
for (register int i=0; i<deep; ++i)
temp*=degree;
return (temp-1)/(degree-1);
}
void change(int* number_a,int* number_b)
{
int temp=*number_a;
*number_a=*number_b;
*number_b=temp;
}
block* create_block(int input_number, int input_deep, block* input_head)
{
block* temp_block=(block*)malloc(sizeof(block));
line[input_number]=temp_block;
temp_block->number=input_number+1;
temp_block->default_number=input_number;
temp_block->deep=input_deep;
temp_block->head=input_head;
temp_block->maximum=get_number_nodes(degree, deep)-degree*(get_number_nodes(degree, deep-input_deep));
temp_block->next=(block**)malloc(sizeof(block*)*degree);
if (input_deep!=deep)
{
for (register int i=0; i<degree; ++i)
temp_block->next[i]=create_block(i+get_number_nodes(degree, input_deep)+degree*(input_number-get_number_nodes(degree, input_deep-1)),input_deep+1, temp_block);
}
return temp_block;
}
void prv_process_block( int block_number)
{
block* temp_block=line[block_number];
if (temp_block->deep==deep)
plus_process();
else
{
int* sub_line;
int remain=get_number_nodes(degree,deep)-get_number_nodes(degree,line[block_number]->deep-1);
int number_of_one=get_number_nodes(degree,line[block_number]->deep)-get_number_nodes(degree,line[block_number]->deep-1);
sub_line=(int*)malloc(sizeof(int)*remain);
for (register int i=0; i<remain; ++i)
{
if (i<number_of_one)
sub_line[i]=1;
else
sub_line[i]=0;
}
for (int process_combination=0; process_combination<Get_combination(remain,number_of_one); ++process_combination)
{
int such_point=0;
for (register int i=0; i<number_of_one; ++i)
{
while (0==sub_line[such_point])
++such_point;
change(&line[temp_block->default_number+i]->number,&line[such_point+get_number_nodes(degree,line[block_number]->deep-1)]->number);
++such_point;
}
if (!((temp_block->head!=NULL&&temp_block->head->number > temp_block->number)||temp_block->number > temp_block->maximum))
prv_process_block(get_number_nodes(degree,line[block_number]->deep));
for (register int i=number_of_one-1; i>=0; --i)
{
if (such_point>=remain)
such_point=remain-1;
while (0==sub_line[such_point])
--such_point;
change(&line[temp_block->default_number+i]->number,&line[such_point+get_number_nodes(degree,line[block_number]->deep-1)]->number);
--such_point;
}
Block_move_process(sub_line,remain);
}
free(sub_line);
}
}
void plus_process()
{
int block_number=1;//get_now_nodes(degree,deep-1);// 임시
unsigned _int64 result_number=1;
while (1)
{
int* sub_line;
int sub_nodes=get_number_nodes(degree,line[block_number]->deep-1), now_nodes=get_number_nodes(degree,line[block_number]->deep);
sub_line=(int*)malloc(sizeof(int)*(get_number_nodes(degree,line[block_number]->deep)-get_number_nodes(degree,line[block_number]->deep-1)));
int last_number=0;
for (register int i=sub_nodes; i<now_nodes; ++i)
sub_line[i-sub_nodes]=0;
for (register int i=sub_nodes; i<now_nodes; ++i)
{
//가장 작은 수를 찾는다.
int now_number=number_nodes;
for (register int j=sub_nodes; j<now_nodes; ++j)
{
if (last_number<line[j]->number && line[j]->number<now_number)
now_number=line[j]->number;
}
// 새로운 결과를 찾는다.
unsigned _int64 new_result=0;
for (register int j=get_number_nodes(degree,deep-2)-1; j<sub_nodes; ++j)
{
if (line[j]->number<now_number)
{
for (register int k=0; k<degree; ++k)
{
if (0==sub_line[line[j]->next[k]->default_number-sub_nodes])
{
if (0==new_result)
sub_line[line[j]->next[k]->default_number-sub_nodes]=now_number;
++new_result;
}
}
}
}
result_number*=new_result;
if (0==new_result)
break;
last_number=now_number;
}
free(sub_line);
if (line[block_number]->deep==deep)
break;
block_number=get_number_nodes(degree,line[block_number]->deep);
}
answer_number+=result_number;
}
int Get_combination(int number_left, int number_right)
{
int bun_ja=1, bun_mo=1;
for (register int i=0; i<number_right; ++i)
{
bun_ja*=number_left-i;
bun_mo*=i+1;
}
return bun_ja/bun_mo;
}
void Block_move_process(int* line, int gaesu)
{
int end=gaesu-1;
int find_last=end;
for (; find_last>=0; --find_last)
{
if (1==line[find_last])
break;
}
if (find_last==end)
{
int gaesu_of_one=0;
int find_zero=0;
for (register int j=end; j>=0; --j)
{
if (0==line[j])
find_zero=1;
else
{
line[j]=0;
if (0==find_zero)
++gaesu_of_one;
else
{
for (register int k=j+1; k<j+2+gaesu_of_one; ++k )
line[k]=1;
break;
}
}
}
}
else
{
line[find_last]=0;
line[find_last+1]=1;
}
}
