~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);
}
}
}
~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;
}
}