Donghua oj advanced question 57 number game

57 digital games

Author: xxx time limit: 1S chapter: recursion

Problem Description:

Now, there are many digital games for children. These games are easy to play, but it is not so easy to create one. Here, we will introduce an interesting game.

You'll get N positive integers. You can concatenate one integer with another to make a larger integer. For example, there are four numbers 123, 124, 56,
90, they can make the following integers - 1231245690, 1241235690, 5612312490, 9012312456,
9056124123… Wait, a total of 24 (4!) numbers can be combined. But 9056124123 is the biggest one.

You may think it's a simple thing, but is it a simple task for a child who just has a digital concept

The input contains multiple sets of test data.

Each group of test data has two lines, the first line is a positive integer N (N < = 50), and the second line has N positive integers.

When N=0, it means the end of input.

Output Description:

For each set of test data, output a row, and output the largest integer that can be combined with these N integers.

Input example: 5 123 124 56 90 9 11 5 991 9909 99 990 989 2 191 1919 0
Output example: 99056124123 1 999919909990989 1919191

At first, I didn't deal with recursion, and there was no problem with the test results, but the prompt timed out after submission. In fact, it can also be understood that if N takes 50, 50! Call times, no timeout.
Original code:

/*
	T57 Digital game 
	Algorithm overview: store the concatenated number with string, and set the string to null at the beginning 
	The given number is traversed first according to the sequence number from small to large depth, and the currently selected number is spliced into the above string every time
	At the last level of recursion, the final string is compared with the current maximum string, and the maximum number is updated 
*/ 

#include<stdio.h>
#include<stdlib.h>  
#include<string.h> 
#define MAX_SIZE 1000

int N = 0;
int flag[55];// flag[i] indicates that the number with subscript i in nums has been selected 
int nums[55] = {0};// Number given
char max[MAX_SIZE] = "";// String of the largest number 
void DFS(char res[], int index, int layer);

int main() {
	
	int i = 0; 
	char res[MAX_SIZE] = "";// Results of digital splicing 
	
//	res[0] = '\0';
//	itoa(123456, res, 10);
	//printf("%s\n", itoa(123456, res, 10));
	
	while (scanf("%d", &N) != EOF) {
		if (N == 0)
			break;
		
		for (i = 1; i <= N; i++)
			scanf("%d", &nums[i]);
		        
		//nums[1] = 991, nums[2] = 9909, nums[3] = 99, nums[4] = 990, nums[5] = 989; 
			
		for (i = 1; i <= N; i++) {// Depth first traversal from small to large 
			res[0] = '\0';// Reset results 
			memset(flag, 0, sizeof(flag));// Reset mark 
			flag[i] = 1; 
			DFS(res, i, 1); 
		}
		
		printf("%s\n", max); 
	}
	
	return 0;
}

// Depth first digit 
// res represents the result of digital splicing, index represents the subscript of the currently selected number, and layer represents the number of layers of current recursion 
void DFS(char res[], int index, int layer) {
	char temp[20] = "";// For numeric to string
	char oriRes[MAX_SIZE] = "";// The original result of each layer of recursion 
	int i = 0;
	
	strcpy(oriRes, strcat(res, itoa(nums[index], temp, 10)));// Splicing 
	
	if (layer == N) {// Recursive export  
		if (strcmp(res, max) == 1)// Only when strcmp(res, max) returns 1 and - 1 can execute, so the result will be wrong 
			strcpy(max, res);// Update Max 
		flag[index] = 0;// De sign	
		
		return ; 
	}
	
	for (i = 1; i <= N; i++) {// Choose another number 
		if (!flag[i]) {// If the current number is not selected 
			flag[i] = 1;
			strcpy(res, oriRes);// Reset results 
			DFS(res, i, layer + 1);
		}
	}
	flag[index] = 0;// De sign 
} 

Later, I thought that when there was res = "989", max="999 *******" this situation, the current recursive path actually didn't need to go on, because the results are the same, you can reduce the number of recursions according to this pruning.

// Judge whether pruning is needed 
int isCapable(char res[], char max[]) {
	int len1 = strlen(res);
	int len2 = strlen(max);
	int len = len1 < len2 ? len1 : len2;
	int i = 0;
	
	for (i = 0; i < len; i++) {
		// The number of res is smaller than that of max, so the current recursive path can be cut out 
		if ((res[i] - '0') < (max[i] - '0')) {
			//printf("+++%c %c\n", res[i], max[i]);
			return 1;
		}
		if ((res[i] - '0') > (max[i] - '0')) {
			return 0;
		}
	}
	return 0;
}

And it did decrease




Many times, but still overtime
Timeout full code:

/*
	T57 Digital game 
	Algorithm overview: store the concatenated number with string, and set the string to null at the beginning 
	The given number is traversed first according to the sequence number from small to large depth, and the currently selected number is spliced into the above string every time
	At the last level of recursion, the final string is compared with the current maximum string, and the maximum number is updated 
*/ 

#include<stdio.h>
#include<stdlib.h>  
#include<string.h> 
#define MAX_SIZE 1000

int N = 0;
int count = 0; 
int flag[55];// flag[i] indicates that the number with subscript i in nums has been selected 
int nums[55] = {0};// Number given
char max[MAX_SIZE] = "";// String of the largest number 
void DFS(char res[], int index, int layer);
int isCapable(char res[], char max[]);

int main() {
	
	int i = 0; 
	char res[MAX_SIZE] = "";// Results of digital splicing 
	
//	res[0] = '\0';
//	itoa(123456, res, 10);
	//printf("%s\n", itoa(123456, res, 10));
	
	while (scanf("%d", &N) != EOF) {
		if (N == 0)
			break;
			
		count = 0;
//		for (i = 1; i <= N; i++)
//			scanf("%d", &nums[i]);
		        
		nums[1] = 991, nums[2] = 9909, nums[3] = 99, nums[4] = 990, nums[5] = 989; 
			
		for (i = 1; i <= N; i++) {// Depth first traversal from small to large 
			res[0] = '\0';// Reset results 
			memset(flag, 0, sizeof(flag));// Reset mark 
			flag[i] = 1; 
			DFS(res, i, 1); 
		}
		
		printf("%s\n", max); 
		printf("Total call%d second\n", count);
	}
	
	return 0;
}

// Depth first digit 
// res represents the result of digital splicing, index represents the subscript of the currently selected number, and layer represents the number of layers of current recursion 
void DFS(char res[], int index, int layer) {
	char temp[20] = "";// For numeric to string
	char oriRes[MAX_SIZE] = "";// The original result of each layer of recursion 
	int i = 0;
	
	count++;
	
	if (strlen(res) != 0 && isCapable(res, max)) {// Prune 
		//printf("res=%s, max=%s\n", res, max);
		flag[index] = 0;// De sign
		return ;
	}
	
	strcpy(oriRes, strcat(res, itoa(nums[index], temp, 10)));// Splicing 
	
	if (layer == N) {// Recursive export  
		if (strcmp(res, max) == 1)// Only when strcmp(res, max) returns 1 and - 1 can execute, so the result will be wrong 
			strcpy(max, res);// Update Max 
		flag[index] = 0;// De sign	
		
		return ; 
	}
	
	for (i = 1; i <= N; i++) {// Choose another number 
		if (!flag[i]) {// If the current number is not selected 
			flag[i] = 1;
			strcpy(res, oriRes);// Reset results 
			DFS(res, i, layer + 1);
		}
	}
	flag[index] = 0;// De sign 
} 

// Judge whether pruning is needed 
int isCapable(char res[], char max[]) {
	int len1 = strlen(res);
	int len2 = strlen(max);
	int len = len1 < len2 ? len1 : len2;
	int i = 0;
	
	for (i = 0; i < len; i++) {
		// The number of res is smaller than that of max, so the current recursive path can be cut out 
		if ((res[i] - '0') < (max[i] - '0')) {
			//printf("+++%c %c\n", res[i], max[i]);
			return 1;
		}
		if ((res[i] - '0') > (max[i] - '0')) {
			return 0;
		}
	}
	return 0;
}

I don't know how to optimize it. I'll see if there's a God who can do it later

Published 76 original articles, won praise 8, visited 9044
Private letter follow

Posted on Wed, 11 Mar 2020 01:37:37 -0700 by cowboysdude