“This is the 13th day of my participation in the November Gwen Challenge. See details: The Last Gwen Challenge 2021”.
preface
This series is based on a certain language foundation (C, C++, Java, etc.) and basic data structure foundation for algorithm learning column, if feel a little difficult
, it is recommended to understand the premise knowledge before learning oh! This column will use easier to understand the expression to learn the algorithm, if there is a problem in some expressions please also give advice
, if you feel good remember to click
this column shortcut door:
…
Can be absolutely greedy problem
Case1: keyboard input a high-precision positive integer N, after removing any s digits, the remaining digits will form a new positive integer according to the original left or right times. For a given n and s, make the remaining numbers form the minimum of the new number and print it.
Problem analysis:
On the premise that the number of digits is fixed, the value of the highest digit is smaller as possible, which can be solved by greedy strategy. But different data can also lead to different situations, such as hypothesis 1, hypothesis 2, hypothesis 3
Hypothesis 1:
N = “12435863” s=2 (remove two numbers)
start
Compare “1, 2, 4, 3, 5, 8, 6” for the first time
1 is high relative to 2, but it’s less than 2, so it doesn’t change
The second comparison is “1, 2, 4, 3, 5, 8, 6”
2 is high relative to 4, but it’s less than 4, so it doesn’t change
The third comparison is “1, 2, 4, 3, 5, 8, 6”
4 is high relative to 3, but the number is larger than the low 4, so 4 is removed.
The fourth comparison is “1, 2, 3, 5, 8, 6.”
3 is high relative to 5, but it’s less than the low 5, so it doesn’t change
The fifth comparison “1, 2, 3, 5, 8, 6”
5 is high relative to 8, but it’s less than the low 8, so it doesn’t change
The fifth comparison “1, 2, 3, 5, 8, 6”
The 8 is high relative to the 6, but the number is larger than the low 8, so the 8 is removed.
The final output 12356 is the minimum number
The end of the
Therefore, adjacent numbers can only be compared from front to back;
Hypothesis 2:
N = “231183” s=3
start
The first comparison “2, 3, 1, 1, 8, 3”
2 is high relative to 3, but it’s less than 3, so it doesn’t change
The second comparison is “2, 3, 1, 1, 8, 3”
I get 2, 1, 1, 8, 3.
3 is high relative to 1, but the number is greater than the low 1, so 3 is removed.
The third comparison is “2, 1, 1, 8, 3.”
The 2 is high relative to the 1, but the number is greater than the low 1, so the 2 is removed.
I get 1, 1, 8, 3.
The fourth comparison is “1, 1, 8, 3.”
1 is high relative to 1, so they’re equal to each other, so they don’t change
The fifth comparison “1, 1, 8, 3”
1 is high relative to 8, but it’s less than the low 8, so it doesn’t change
The sixth comparison “1, 1, 8, 3”
The 8 is high relative to the 1, but the number is larger than the low 1, so the 8 is removed
I get 1, 1, 3.
The final output of 113 is the minimum number
The end of the
Therefore, we can compare the i-th bit with the I-th +1 bit. After deleting the i-th bit, we must consider the i-1st bit and the I-th +1 bit to ensure the correctness of the result.
Hypothesis 3:
N = “123456” s=3
It can be clearly seen that there is no need to delete the adjacent digits. In this case, the last three digits should be deleted, that is, the minimum value is 123
Of course, there is another possibility
Hypothesis 3-1
N =”120083″ s=3
1 0 0 8 3
2 is greater than 0, so “0, 0, 8, 3”
Eight is more than three, which is zero, zero, three.
Minimum of 3
Therefore, when n contains 0, when some numbers are deleted, the digit 0 May appear in the high position of the result, and it is unreasonable to directly output this data. You should remove all the high zeros before printing. In particular, consider that if the result string is 0000, instead of deleting all zeros, one “0” should be left for final output
Therefore, from the above assumptions, in algorithm design, a large number of different examples from concrete to abstract induction must be selected to fully understand and experience the process of problem solving, rules and various different situations, so as to design a correct algorithm.
Algorithm design:
delete(char[].int b,int k){
int i;
for(i=b; i<length(n)-k; i++){ n[i]=n[i+k]; } main(){char n[100];
int s,i,j,j1,c,data [100],len;
cin>>n>>s;//n is a positive integer, minus s digits
len=length(n);
}
if(s>len){
cout<<"Data error!";
return;
}
j1=0;
for(i=1; i<=s; i++){ {for(j=1; j<length(n); j=j+1)
{
if(n[j]>n[j+1]) {// Greedy choice
delete(n,j,1);
}
if(j>j1){
data[i]=j+i; // Record the location of the deleted number
}else{ // Suppose 2 is deleted forward
data[i]=data[i-1] -1;
}
j1=j;
break;
}
if(j>length(n)){
break;
}
for(i=i; i<=s; i++){ j=len-i+1;
delete(n,j,1);
data[i]=j;
} while(n[1] ='0' && length(n)>1){
delete(n,1.1); // Remove the zeros at the beginning of the string
cout<<n;
for(i=1; i<=s; i++){ cout<<data[i]<<' ';
}
}
}
}
}
Copy the codeTo sum up: The algorithm is mainly composed of four parts: initialization, comparison of adjacent digits (deletion if necessary), handling the situation that not enough S bits are deleted in the comparison process and the output of the result.
Postscript tail
This is the end of this article. I am Zeus
