catalogue
A diamond pattern
Title Description
KiKi learned the cycle, and teacher BoBo gave him a series of practice of printing patterns. The task is to print diamond patterns composed of "*".
input
Multiple sets of inputs, an integer (2 ~ 20).
output
For each line of input, the output is a diamond composed of "*", with a space after each "*". A blank line is required after each output diamond.
Sample input: Copy
2
3
4
Sample output: Copy
*
* *
* * *
* *
*
*
* *
* * *
* * * *
* * *
* *
*
*
* *
* * *
* * * *
* * * * *
* * * *
* * *
* *
*
Analysis: this question is still relatively simple. It is a question of law. If you are serious, you can usually write it out.
Clarify the relationship between * and spaces.
Obviously, there are two steps. First output spaces, and then output '*' (* plus spaces).
I won't tremble. Just look at the code and understand it directly.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int main (){
int n;
while(~scanf("%d",&n)){
solve (n);
printf("\n");
}
return 0;
}
void solve (int n){
for(int i=0;i<=n;i++)
{
for(int j=0;j<n-i;j++)
printf(" ");
for(int j=0;j<=i;j++)
printf("* ");
printf("\n");
}
for(int i=n-1;i>=0;i--)
{
for(int j=0;j<n-i;j++)
printf(" ");
for(int j=0;j<=i;j++)
printf("* ");
printf("\n");
}
}B Niu Mei's cake
Title Description
As we all know, Niu Mei likes cake very much.
On the first day, Niu Mei ate more than one-third of the total number of cakes. On the second day, she ate more than one-third of the remaining cakes. Later, she ate more than one-third of the remaining cakes of the previous day every day. When she was ready to eat on the n day, there was only one cake left.
Niu Mei wants to know how many cakes there were when she started eating on the first day?
input
Enter n, 0 < n < 30.
output
Output the number of cakes on the first day.
Sample input: Copy
2
4
Sample output: Copy
3
10
Analysis: just find rules. If the cake of the previous day is x, then the remaining cake of this day is 2/3 *x-1;
Then we can push back and forward, starting from 1, (1 + 1) * 3 / 2;
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int main (){
int n;
while(~scanf("%d",&n)){
int x=1;
for(int i=1;i<n;i++)
x=(x+1)*3/2;
printf("%d",x);
printf("\n");
x=0;
}
return 0;
}C. Nichols theorem
Title Description
Verify nikochus theorem, that is, the cube of any integer m can be written as the sum of m consecutive odd numbers.
For example:
1^3=1
2^3=3+5
3^3=7+9+11
4^3=13+15+17+19
input
Multiple sets of inputs, enter an integer.
output
Output the decomposed string.
Sample input: Copy
6
Sample output: Copy
31+33+35+37+39+41
Analysis: this problem is still the problem of finding rules; Before, I also thought about adding the left cube and the right sum, and then cycling. If they are equal, they will output.
Later, it was found that there was a more reliable law.
That is, first square the number, and then {a loop ok. The first number to be output is always equal to the square number - n +1;
Whether n is even or odd, it's the same. Then you can add 2 to the loop.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main (){
int n;
while(~scanf("%d",&n)){
int a[n];
int z=solve(a,n);
}
return 0;
}
int solve (int a[],int n){
int lfs=n*n*n;
int sum=0;
int pfs=n*n;
for(int i=0;i<n;i++)
a[i]=pfs-n+1+i*2;
for(int i=0;i<n-1;i++)
printf("%d+",a[i]);
printf("%d",a[n-1]);
printf("\n");
}D ABC+DEF=GHI
Title Description
With 1, 2, 3 9 these nine numbers form a mathematical formula, which meets the following requirements: ABC + DEF = GHI, each number can only appear once, and write a program to output all combinations.
input
nothing
output
Output all ABC + DEF = GHI,
One piece of data per line, in the format of ABC+DEF=GHI
The output results are arranged in ascending order of ABC. If ABC is the same, they are arranged in ascending order of DEF.
Analysis: this problem is the same as the nine array fraction problem I learned before.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int a[9];
int v[9];
int main (){
digui(1);
return 0;
}
void digui (int k){
if(k==10) {
if((a[1]*1000+a[2]*100+a[3]*10+a[4])*3 == a[5]*10000+a[6]*1000+a[7]*100+a[8]*10+a[9] ){
printf("%d%d%d%d/%d%d%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
return ;
}
}
else{
for(int i=1;i<=9;i++)
{
if(v[i]==0){
a[k]=i;
v[i]=1;
digui(k+1);
v[i]=0;
}
}
}
}E. oilfield problems
Title Description
Enter a character matrix of m rows and n columns to count the number of octets formed by the character "@". If the grid where the two characters "@" are located is adjacent (horizontal, vertical or diagonal direction), they belong to the same octet.
input
Multi group input
Enter the number of rows m and the number of columns n.
Then enter * and@
1<=n,m<=100
output
Number of connected blocks
Sample input: Copy
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
Sample output: Copy
2
Analysis: the backtracking method is actually recursion, like the oil field problem, which is completely recursion with a pruning function.
In fact, if you look at the code and draw a recursive tree manually, it will be clearer.
Where's the pruning? One is to see whether it is out of bounds, and the other is whether it is marked when it is @ or not.
The next step is to loop @, recurse @, and find similar @.
See code analysis for details:
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
char pic[200][200];
int idx[200][200];
int count=0;
int n;
int m;
int main (){
while(~scanf("%d %d",&m,&n)){
for(int i=0;i<m;i++)
scanf("%s",pic[i]);
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if(idx[i][j]==0&&pic[i][j]=='@') solve(i,j,++count);
}
printf("%d",count);
printf("\n");
count=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
idx[i][j]=0;
}
return 0;
}
void solve (int r,int c,int id){
if(r<0||r>=m||c<0||c>=n) return;
if(idx[r][c]>0||pic[r][c]!='@') return;
idx[r][c]=id;
for(int i=-1;i<=1;i++)
for(int j=-1;j<=1;j++)
if(i!=0||j!=0) solve(r+i,c+j,id);
}Ergodic problem of F-horse
Title Description
In the 5 * 4 chessboard, the horse can only walk obliquely. The horse starts from position (x, y) and walks each grid of the chessboard once and only once. Please find out all paths.
input
x. Y represents the initial position of the horse.
output
The total number of paths to take each grid once. If the path does not exist, "No solution!" is output.
Sample input: Copy
1 1
2 2
Sample output: Copy
32
No solution!
Analysis: this problem, how to say, such backtracking problems can be used for general solution.
You can draw recursive trees to understand them, so it's useless to say more. You should look at code analysis and draw a picture yourself.
The method is the pruning function, as long as it is marked or out of bounds.
Then there is the recursion of {eight positions. Once all the lattices are reached, you can add 1 to the number of solutions.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int A[200][200];
int n=5;
int m=4;
int count=0;
int fx[8]={1,2,2,1,-1,-2,-2,-1};
int fy[8]={2,1,-1,-2,-2,-1,1,2};
int main (){
int x;
int y;
while(~scanf("%d %d",&x,&y)){
solve(x,y,1);
if(count!=0)
printf("%d",count);
else{
printf("No solution!");
}
printf("\n");
count=0;
}
return 0;
}
void solve(int x,int y,int step){
int nextx;
int nexty;
A[x][y]=step;
if(n*m==step) count++;
for(int i=0;i<=7;i++)
{
nextx=x+fx[i];
nexty=y+fy[i];
if(check(nextx,nexty))
solve(nextx,nexty,step+1);
}
A[x][y]=0;
}
int check(int x,int y){
if(x>=1&&x<=n&&y>=1&&y<=m&&A[x][y]==0)
return 1;
else return 0;
}