There were five people A, B, C, D and E, and each of them had a piece of black or white paper on their foreheads. Five people sat opposite each other, and each could see the color of the paper on the foreheads of others. After the five people observed each other,
A said: "I saw three people putting white paper on their foreheads and one person putting black paper on their foreheads."
B said: "I saw that the other four people were covered with black paper on their foreheads."
C said: "I saw that one person's forehead was covered with white paper, and the other three people's forehead was covered with black paper."
D said: "I saw that all four people posted white paper on their foreheads."
E said nothing.
Now it is known that people who post black paper on their foreheads are telling lies, and people who post white paper on their foreheads are telling the truth. Ask these five people who have white paper on their foreheads and whose foreheads are black paper?
*Problem analysis and algorithm design
If the variables A, B, C, D, and E represent the color of the paper posted on each person’s forehead, 0 represents black, and 1 represents white. Based on what A, B, C and D said in the question, the following relationship can be summarized:
A says: a&&b+c+d+e==3||!a&&b+c+d+e!=3
B says: b&&a+c+d+e==0||!b&&a+c+d+e!=0
C says: c&&a+b+d+e==1||!c&&a+b+d+e!=1
D says: d&&a+b+c+e==4||!d&&a+b+c+e!=4
Extract all possible situations of the color of the paper on everyone's forehead and substitute it into the above expression for reasoning operations, so that the above expression is "true" is the correct result.
*Program description and comments
#include<>
int main()
{
int a,b,c,d,e;
for(a=0;a<=1;a++) /*Black: 0 White: 1*/
for(b=0;b<=1;b++) /*Exhaust all the possibilities of five people posting paper on their foreheads*/
for(c=0;c<=1;c++)
for(d=0;d<=1;d++)
for(e=0;e<=1;e++)
if((a&&b+c+d+e==3||!a&&b+c+d+e!=3)
&&(b&&a+c+d+e==0||!b&&a+c+d+e!=0)
&&(c&&a+b+d+e==1||!c&&a+b+d+e!=1)
&&(d&&a+b+c+e==4||!d&&a+b+c+e!=4))
{
printf("A is pasted a piece of %s paper on his forehead.\n",
a?"white":"black");
printf("B is pasted a piece of %s paper on his forehead.\n",
b?"white":"black");
printf("C is pasted a piece of %s paper on his forehead.\n",
c?"white":"black");
printf("D is pasted a piece of %s paper on his forehead.\n",
d?"white":"black");
printf("E is pasted a piece of %s paper on his forehead.\n",
e?"white":"black");
}
}
*Run result
A is pasted a paper of black paper on his forehead. (Black)
B is pasted a paper of black paper on his forehead. (Black)
C is pasted a paper of white paper on his forehead. (White)
D is pasted a paper of black paper on his forehead. (Black)
E is pasted a paper of white paper on his forehead. (White)
53.Doctor Mystery’s Problem (1)
The honest tribe and the lying tribe are different ethnic groups from two desert islands. People from the honest tribe always tell the truth, while people from the lying tribe always tell lies. Dr. Miyu is a smart person. He wants to judge which ethnic group the person he meets comes from.
Dr. Myoyu meets three people and knows that they may be from the Honest or Liars. To investigate what tribe these three people are, the doctor asked their questions separately, and here are their conversations:
Ask the first person: "What kind of tribe are you?" and answer: "Two of us are from the honest tribe." The second person said: "Don't talk nonsense, only one of the three of us is from the honest tribe." After hearing the second person's words, "Yes, there is only one honest tribe."
Please judge which tribe they belong to based on his answer.
*Problem analysis and algorithm design
Suppose these three people are A, B, and C respectively. If you lie, its value is 0, and if you are honest, its value is 1. According to the words of the three people in the question, they can be listed separately:
The first person: a&&a+b+c==2||!a&&a+b+c!=2
The second person: b&&a+b+c==1||!b&&a+b+c!=1
The third person: c&&a+b+c==1||!c&&a+b+c!=1
Using exhaustive methods, results can be easily derived.
*Program description and comments
#include<>
int main()
{
int a,b,c;
for(a=0;a<=1;a++) /*Exhaust all the situations of whether everyone is lying or being honest*/
for(b=0;b<=1;b++) /*Ly: 0 Honesty: 1*/
for(c=0;c<=1;c++)
if((a&&a+b+c==2||!a&&a+b+c!=2) /*Judge whether the question is satisfied*/
&&(b&&a+b+c==1||!b&&a+b+c!=1)
&&(c&&a+b+c==1||!c&&a+b+c!=1))
{
printf("A is a %s.\n",a?"honest":"lier"); /*Output judgment result*/
printf("B is a %s.\n",b?"honest":"lier");
printf("C is a %s.\n",c?"honest":"lier");
}
}
*Run result
A is a lier
B is a lier (liars)
C is a lier
*Thoughts
Dr. Myoyu meets four people and knows that they may be from the Honest and Liars. In order to investigate what tribe these four people are, the doctor asked as usual: "What tribe are you from?"
The first person said: "All four of us are from the lie race."
The second person said: "Only one of us is from the lie group."
The third person said: "Two of the four of us are from the lie clan."
The fourth person said: "I am from the honest tribe."
Ask if the fourth person who claims to be the "Honest Clan" is really from the Honest Clan?
(Answer: The fourth person is from the honest clan.)
54. The Problem of Doctor Myth (2)
The two-sided tribe is a new nation on the deserted island. Their characteristics are that they speak real and false and alter true and false. If the first sentence is true, then the second sentence is false; if the first sentence is false, then the second sentence is true, but there is no rule whether the first sentence is true or false.
Dr. Myoyu met three people and knew that they came from three different ethnic groups: the honest, the lie and the two-faced. The three of them stood shoulder to shoulder in front of the doctor.
The doctor asked the person on the left: "What tribe is the person in the middle?", and the person on the left answered: "The honest tribe."
The doctor asked the middle man: "What kind of tribe are you from?", and the middle man replied: "Two-faced tribe."
The doctor asked the person on the right: "What kind of tribe is the person in the middle?", and the person on the right answered: "The person in the liars".
May I ask: Which ethnic group do these three people belong to?
*Problem analysis and algorithm design
This problem is the most basic problem among the two-faced tribe problem, and it is more complicated than the previous problem of only the honest tribe and the lying tribe. When solving the problem, you should use variables to express these three ethnic groups separately.
Let: variable A=1 means: the person on the left is from the honest family (denoted as A in C language);
The variable B=1 means: the person in the middle is from the honest family (represented as B in C);
The variable C=1 means: the person on the right is from the honest family (denoted as C in C);
The variable AA=1 means: the person on the left is a two-faced family (denoted as AA in C language);
The variable BB=1 means: the person in the middle is a two-faced family (represented as BB in C language);
The variable CC=1 means: the person on the right is a two-faced family (represented as CC in C language);
Then the person on the left is a lying clan, which can be expressed as: A!=1 and AA!=1 (not the honest clan and the two-faced clan)
In C language, it is expressed as:!A&&!AA
The person in the middle is a lie group, which can be expressed as: B!=1 and BB!=1
In C language, it is expressed as:!B&&!BB
The person on the right is a lie clan, which can be expressed as: C!=0 and CC!=1
In C language, it is expressed as: !C&&!CC
According to the conditions in the title "Three people come from three ethnic groups", you can list:
a+aa!=2&&b+bb!=2&&c+cc!=2 and a+b+c==1&&aa+bb+cc==1
According to the answer of the person on the left, it can be said that if they are honest tribes, the people in the middle are also honest tribes; if they are not honest tribes, the people in the middle are not honest tribes. The above conditions can be expressed as:
c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&&cc
Join all logical conditions together and use exhaustive methods to solve them. Any variable that makes the above conditions hold at the same time is the answer to the question.
*Program description and comments
#include<>
int main()
{
int a,b,c,aa,bb,cc;
for(a=0;a<=1;a++) /*Exhausted all situations*/
for(b=0;b<=1;b++)
for(c=0;c<=1;c++)
for(aa=0;aa<=1;aa++)
for(bb=0;bb<=1;bb++)
for(cc=0;cc<=1;cc++)
if(a+aa!=2&&b+bb!=2&&c+cc!=2&& /*Judge logical conditions*/
a+b+c==1&&aa+bb+cc==1 &&
(a&&!aa&&b&&!bb||!a&&!b)&&
!b &&
(c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&cc))
{
printf("The man stand on left is a %s.\n",
aa?"double–dealer":(a?"honest":"lier"));
printf("The man stand on left is a %s.\n",
bb?"double–dealer":(b?"honest":"lier"));
printf("The man stand on left is a %s.\n",
cc?"double–dealer":(c?"honest":"lier"));
/*Output the final inference result*/
}
}
*Run result
The man stand on left is a double–dealer.
The man stand on center is a lier.
The man stand on right is a honest.
*Thoughts
When Doctor Miyu met three people, he asked the first person: "What tribe are you from?" and answered: "The Honesty Clan." Asked the second person: "What tribe are you from?" and answered: "What tribe are you from?" and answered: "The Lie Clan." The doctor asked the second person: "Is the first person really from the Honesty Clan?" and answered: "Yes." Asked the third person: "What tribe are you from?" and answered: "What tribe are you from?" and answered: "What tribe is the first person?" and answered: "The two-faced clan."
Please determine which ethnic group this person belongs to?
(Answer: The first person is from the honest tribe, the second person is from the two-faced tribe, and the third person is from the lying tribe.)
55. Which doctor is on duty on that day
The hospital has seven doctors A, B, C, D, E, F, and G. Each person has to take turns to work for one day within one week (Monday to Sunday). Now known:
Doctor A is on duty one day later than Doctor C;
Doctor D is on duty two days later than Doctor E;
Doctor B is on duty three days earlier than Doctor G;
Doctor F’s duty day is between Doctor B and C, and it is Thursday;
Please determine which doctor is on duty every day?
*Problem analysis and algorithm design
From the question, the following known conditions can be derived:
*F is on duty on Thursday;
*B duty date is Monday to Wednesday, and G duty is three days later;
*C's duty date is from Friday to Saturday, and one day later is A's duty;
*E will be on duty after two days; E can only be on duty from Monday to Wednesday;
When programming, use the subscripts of array elements to represent Monday to Sunday, and use the values of array elements to represent seven doctors A to F respectively.
*Program description and comments
#include<>
#include<>
int a[8];
char *day[]={"","MONDAY","TUESDAY","WEDNESDAY","THURSDAYT",
"FRIDAY","SATUDAY","SUNDAY"}; /*Create the week table*/
int main()
{
int i,j,t;
a[4]=6; /* Thursday is F on duty*/
for(i=1;i<=3;i++)
{
a[i]=2; /*Suppose the date of B's duty*/
if(!a[i+3]) a[i+3]=7; /*If there is no one on duty after three days, arrange G on duty*/
else{ a[i]=0;continue;} /* Otherwise, the date of B's duty will be constantly correct*/
for(t=1;t<=3;t++) /*Suppose the time of E on duty*/
{
if(!a[t]) a[t]=5; /*If there is no one on duty on that day, E will be on duty*/
else continue;
if(!a[t+2]) a[t+2]=4; /*If E is on duty for two days, it should be D*/
else{ a[t]=0;continue;} /* Otherwise, the date of E on duty is incorrect*/
for(j=5;j<7;j++)
{
if(!a[j]) a[j]=3; /*If there is no one on duty on that day, then arrange C on duty*/
else continue;
if(!a[j+1]) a[j+1]=1; /*No one is on duty for one day after C, then A should be on duty*/
else{ a[j]=0;continue;} /* Otherwise, the A duty date is incorrect*/
for(i=1;i<=7;i++) /*After arrangement, output result*/
printf("Doctor %c is on duty %s.\n",'A'+a[i]-1,day[i]);
exit(0);
}
}
}
}
*Run result
Doctor E is on duty MONDAY. (Monday: E)
Doctor B is on duty TUESDAY. (Tuesday: B)
Doctor D is on duty WEDNESDAY. (Wednesday: D)
Doctor F is on duty THUESDAY. (Thursday: F)
Doctor G is on duty FRIDAY. (Friday: G)
Doctor C is on duty SATURDAY. (Saturday: C)
Doctor A is on duty SUNDAY. (Sunday: A)
*Thoughts
During the solution to this problem, we only considered the situation within one week and did not consider the situation across the week. The condition for "Doctor B is on duty three days earlier than Doctor G" is simply considered to be three days earlier than Doctor G. If you consider cross-week situations, it may occur: Doctor B is on duty on Monday, while Doctor G is on Friday last week. Similarly, the condition that "Doctor F's duty day is between Doctor B and Doctor C" can also be expanded to: "As long as Doctor F's duty day is between Doctor B and Doctor C, it is fine."
Please consider possible schedules where cross-week situations are allowed.
56. Distinguish the nationality of a traveler
There are six people of different nationalities living in a hotel, from the United States, Germany, Britain, France, Russia and Italy. Their names are A, B, C, D, E and F. The order of names does not necessarily correspond to the nationality above. Now known:
1)A Americans are doctors.
2) E and the Russians are technicians.
3) C and Germans are technicians.
4) B and F have served as soldiers, but the Germans have never joined the army.
5) French people are older than A; Italians are older than C.
6) B and Americans will travel to Xi'an next week, while C and French will go to Hangzhou for vacation next week.
Based on the above known conditions, which country are A, B, C, D, E and F from each?
*Problem analysis and algorithm design
First, conduct a question analysis and use known conditions as much as possible to determine who is not from which country.
From: 1) 2) 3) It can be seen that A is not an American, E is not a Russian, and C is not a German. In addition, because A is different from the profession of Germans, E is different from the profession of Americans and Germans, and C is different from the profession of Americans and Russians, so A is not a Russian or German, E is not an American or German, and C is not an American or Russian.
From 4) and 5) we can see that B and F are not Germans, A is not French, and C is not Italian.
From 6) we can see that B is not an American or a Frenchman (because B is different from the French travel location next week); C is not a Frenchman.
Summarize the above results to obtain the following condition matrix:
. American (doctor) British, French, German (technician) Italy Russian (teacher)
A(Doctor) X. X. X. X
B X . X X . .
C (Technician) X. X X X X
D . . . . . .
E(Teacher) X . . X . X
F . . . X . .
According to this table, you can easily get the answer to the question.
It is easy to input the condition matrix into the computer and implement the elimination algorithm with programs.
*Program description and comments
#include<>
char *m[7]={" ","","","FRANCE","GER","ITALI","EUSSIAN"}; /*National name*/
int main()
{
int a[7][7],i,j,t,e,x,y;
for(i=0;i<7;i++) /*Initialization condition matrix*/
for(j=0;j<7;j++) /*Actor, listed as a country, the value of the element indicates that someone is the country*/
a[i][j]=j;
for(i=1;i<7;i++) /*Element 0 of each column of the condition matrix is used as the mark for data processing of this column*/
a[0][i]=1; /*Tag this column has not been processed yet*/
a[1][1]=a[2][1]=a[3][1]=a[5][1]=0; /*Enter various conditions in the condition matrix*/
a[1][3]=a[2][3]=a[3][3]=0; /*0 means that people are not from the country*/
a[1][4]=a[2][4]=a[3][4]=a[5][4]=a[6][4]=0;
a[3][5]=0;
a[1][6]=a[3][6]=a[5][6]=0;
while(a[0][1]+a[0][2]+a[0][3]+a[0][4]+a[0][5]+a[0][6]>0)
{ /*Exit the loop after all six columns are processed*/
for(i=1;i<7;i++) /*i:Column coordinates*/
if(a[0][i]) /*If the column has not been processed yet, then process it*/
{
for(e=0,j=1;j<7;j++) /*j:Line coordinates e:Non-0 element counter in this column*/
if(a[j][i]) { x=j;y=i;e++;}
if(e==1) /*If there is only one element in this column that is non-zero, then perform an elimination operation*/
{
for(t=1;t<7;t++)
if(t!=i)a[x][t]=0; /*Set other elements of the row where the non-zero element is located 0*/
a[0][y]=0; /*Set the flag that has been processed in this column*/
}
}
}
for(i=1;i<7;i++) /*Output inference result*/
{
printf("%c is coming from ",'A'-1+i);
for(j=1;j<7;j++)
if(a[i][j]!=0)
{ printf("%s.\n",m[a[i][j>); break;}
}
}
*Run result
A is coming from ITALY. (Italian)
B is coming from EUSSIAN. (Russian)
C is coming from .. (British)
D is coming from GER. (German)
E is coming from FRANCE. (French)
F is coming from .. (American)
* Further discussion of the problem
Generating a conditional matrix and then using the elimination method for inference judgment is a common method. It is very effective in solving more complex logical problems.
*Thoughts
In the geography class, the teacher gave a map of China without specifying the provinces, and selected five provinces from 1 to 5 numbers, and asked everyone to write the names of the provinces. After handing over the paper, each of the five students only answered the names of two provinces as follows, and each of them only answered one province correctly. What is the correct answer?
A: Shaanxi No. 2, Gansu No. 5 B: Hubei No. 2, Shandong No. 4
C Answer: Shandong No. 1, Jilin No. 5 D Answer: Hubei No. 3, Jilin No. 4
E Answer: Gansu No. 2, Shaanxi No. 3
57. Whose child runs the slowest
The Zhang and Li families each have three children. One day, nine children from the three families competed together for a sprint. Regardless of age, they scored 9 points for the first place, scored 8 points for the second place, and so on. The total scores of each family are the same, and these children do not reach the finish line at the same time, and no two or three children in the family get connected rankings. The children of the Li family were known to be the first place, and the children of the Wang family were the second place. Ask whose child was the last one?
*Problem analysis and algorithm design
According to the conditions of the question, there are 1+2+3+…+9=45 points, and the score of each child should be 15 points. According to the question, we can see that the children of the Li family won the first place, and the children of the Wang family won the second place, so we can say that the children of the Zhang family won the third place must be the children of the Zhang family. From "these children did not reach the finish line at the same time", we can see that the rankings cannot be tied, and from "no family of two or three children get connected rankings" we can see that the fourth place cannot be the child of the Zhang family.
For convenience in the program, it is directly expressed by scores.
*Program description and comments
#include<>
int score[4][4];
int main()
{
int i,j,k,who;
score[1][1]=7; /*Initialize according to known conditions: score[1]: The score of the three children of the Zhang family*/
score[2][1]=8; /*score[2]: The scores of the three children of the Wang family*/
score[3][1]=9; /*The scores of the three children of the Li family*/
for(i=4;i<6;i++) /*i: The possible scores of Zhang's children in the 4 to 6 segments*/
for(j=4;j<7;j++) /*j: Possible scores for Wang's children in segments 4 to 6*/
for(k=4;i!=j&&k<7;k++) /*k: Possible scores for Li's children in the 4 to 6th segment*/
if(k!=i&&k!=j&&15-i-score[1][1]!=15-j-score[2][1] /*Scores cannot be paralleled*/
&&15-i-score[1][1]!=15-k-score[3][1]
&&15-j-score[2][1]!=15-k-score[3][1])
{
score[1][2]=i;score[1][3]=15-i-7; /*Record the result that meets the conditions into the array*/
score[2][2]=j;score[2][3]=15-j-8;
score[3][2]=k;score[3][3]=15-k-9;
}
for(who=0,i=1;i<=3;i++,printf("\n"))
for(j=1;j<=3;j++)
{
printf("%d",score[i][j]); /*Output scores of each child*/
if(score[i][j]==1)who=i; /*Record the family number of the last one*/
}
if(who==1) /*Output the final judgment result*/
printf("The last one arrived to end is a child from family Zhang.\n");
else if(who==2)
printf("The last one arrived to end is a child from family Wang.\n");
else printf("The last one arrived to end is a child from family Li.\n");
}
*Run result
7 5 3
8 6 1
9 4 2
The last one arrived to end is a child from family Wang.
(The last one was the Wang family’s child.
58. Latin square array
Construct the NXN order Latin square matrix (2<=N<=9), so that the numbers 1 to N appear only once in each row and column in the square matrix. If N=4:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
*Problem analysis and algorithm design
There are many ways to construct Latin square arrays, and here is the easiest method. Observing the example given, it can be found that if the number in the first column and the number in the last column are connected to form a ring, the ring is exactly composed of 1 to N order; for the i-th row, the starting number of this ring is i. According to this rule, it is easy to write a program. The following is a program for constructing a 6th-order Latin square matrix.
*Program description and comments
#include<>
#define N 6 /*Determine N value*/
int main()
{
int i,j,k,t;
printf("The possble Latin Squares of order %d are:\n",N);
for(j=0;j<N;j++) /*Construct N different Latin square matrix*/
{
for(i=0;i<N;i++)
{
t=(i+j)%N; /*Determine the value of the first element in the i-th row of the Latin matrix*/
for(k=0;k<N;k++) /*Output each element in the line in the form of a ring*/
printf("%d",(k+t)%N+1);
printf("\n");
}
printf("\n");
}
}
*Run result
The possble Latin Squares of order 6 are:
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4
59.Fill in the form
Fill in the table below 1, 2, 3, 4, 5 and 6 so that the numbers on the right of each column are larger than the numbers on the left, and the numbers on the bottom of each row are larger than the numbers on the top. According to this requirement, how many ways to fill in it?
*Problem analysis and algorithm design
Analysis according to the requirements of the question, the number 1 must be placed in the grid of the first row and the first column, and the number 6 must be placed in the grid of the second row and the third column. In implementation, you can use a one-dimensional array to represent, the first three elements represent the first row and the last three elements represent the second row. First, initialize the array according to the original question, and then test according to the requirements for filling in the numbers in the question.
*Program description and comments
#include<>
int jud1(int s[]);
void print(int u[]);
int count; /*Counter*/
int main()
{
static int a[]={1,2,3,4,5,6}; /*Initialize array*/
printf("The possble table satisfied above conditions are:\n");
for(a[1]=a[0]+1;a[1]<=5;++a[1]) /*a[1] must be greater than a[0]*/
for(a[2]=a[1]+1;a[2]<=5;++a[2]) /*a[2] must be greater than a[1]*/
for(a[3]=a[0]+1;a[3]<=5;++a[3]) /*The a[3] in the second line must be greater than a[0]*/
for(a[4]=a[1]>a[3]?a[1]+1:a[3]+1;a[4]<=5;++a[4])
/*The second row a[4] must be greater than the left side a[3] and the upper side a[1]*/
if(jud1(a)) print(a); /*If the question is satisfied, print the result*/
}
int jud1(int s[])
{
int i,l;
for(l=1;l<4;l++)
for(i=l+1;i<5;++i)
if(s[l]==s[i]) return 0; /*If there are duplicate numbers in the array, return 0*/
return 1; /*If the numbers in the array are not repeated, return 1*/
}
void print(int u[])
{
int k;
printf("\nNo.:%d",++count);
for(k=0;k<6;k++)
if(k%3==0) /*Output the first three elements of the array as the first line*/
printf("\n%d",u[k]);
else /*Output the last three elements of the array as the second line*/
printf("%d",u[k]);
}
*Run result
The possble table satisfied above conditions are:
No.1: No.2: No.3: No.4: No.5:
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5
4 5 6 3 5 6 3 4 6 2 5 6 2 4 6
60.1~9 is divided into three 3-digit numbers of 1:2:3
Divide the nine numbers 1 to 9 into three 3-digit numbers, and find the first 3-digit number, which is exactly twice the second 3-digit number and three times the third 3-digit number. Ask how to divide it.
*Problem analysis and algorithm design
There is a mathematical relationship between the three numbers in the problem. In fact, just determine the first three-digit number to solve the problem.
After testing the first three-digit number, calculate the other two numbers, decompose them into three-digit numbers, and then make a judgment to determine whether the number being tested is the answer.
It should be noted that the initial value of the test can be 123 and the maximum value is 333. Because it is impossible to exceed this range.
*Programming and programming
#include<>
int ok(int t,int *z);
int a[9];
int main()
{
int m,count=0;
for(m=123;m<=333;m++) /*Test possible three-digit numbers*/
if(ok(m,a)&&ok(2*m,a+3)&&ok(3*m,a+6)) /*If the question is satisfied*/
printf("No.%d: %d %d %d %d\n",++count,m,2*m,3*m); /*Output result*/
}
int ok(int t,int *z) /*Decompose the value of t and store it into the three array elements pointed to by z. If the requirements are met, return 1*/
{
int *p1,*p2;
for(p1=z;p1<z+3;p1++)
{
*p1=t%10; /*Decompose integer*/
t/=10;
for(p2=a;p2<p1;p2++) /*Query whether the decomposed number has appeared*/
if(*p1==0||*p2==*p1)return 0; /*If repeated, return */
}
return 1; /* Otherwise return 1*/
}
*Run result
No.1:192 384 576
No.2:219 438 657
No.3:273 546 819
No.4:327 654 981
*Thoughts
Find all possible formulas of the following forms, each formula has nine digits, just using up the nine numbers 1 to 9.
1)○○○+○○○=○○○ (There are 168 possible combinations in total)
2)○×○○○○=○○○○ (There are 2 possible combinations in total)
3)○○×○○○=○○○○ (There are 7 possible combinations in total)
4)○×○○○=○○×○○○ (There are 13 possible combinations in total)
5)○×○○○=○×○○○○○ (There are 28 possible combinations in total)
6)○○×○○=○×○○○○○ (There are 7 possible combinations in total)
7)○○×○○=○○×○○○ (There are 11 possible combinations in total)
Hundreds of exquisite explanations of classic, practical and interesting programming of C/C++ language (7)
61.1~9 constitutes three 3-digit square numbers
Divide nine numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 into three groups. Each number can only be used once, that is, there are no repeated numbers in each group, nor are they repeated with the three numbers in other groups. The three digits in each group are required to form a square number.
*Problem analysis and algorithm design
There are many ideas for this problem, and here is a simple and fast algorithm.
First, find a three-digit number that does not contain 0 and is the square of an integer. There are not many such three-digit numbers. The three-digit numbers that meet the conditions are then combined so that the 9 numbers of the selected three three-digit numbers are not repeated.
The process of finding a three-digit number with a sufficient condition can be combined in the program with the process of digitally decomposing the three-digit number.
*Program description and comments
#include<>
int main()
{
int a[20],num[20][3],b[10]; /*a: Store three-digit numbers that meet the conditions*/
/*If it is not a multiple of 10, then decompose the three-digit number*/
/*Decompose each number in the three digits*/
int i,j,k,m,n,t,flag;
printf("The 3 squares with 3 different digits each are:\n");
for(j=0,i=11;i<=31;i++) /*Finding the three-digit number that is a square number*/
if(i%10!=0) /*If it is not a multiple of 10, then decompose the three-digit number*/
{
k=i*i; /*Decompose each number in the three-digit number*/
num[j+1][0]=k/100; /*Hundred digits*/
num[j+1][1]=k/10%10; /*Ten digits*/
num[j+1][2]=k%10; /*single digit*/
if(!(num[j+1][0]==num[j+1][1]||num[j+1][0]==num[j+1][2]||
num[j+1][1]==num[j+1][2])) /*If the three digits of the decomposition are not equal*/
a[++j]=k; /*j: Counter, counting the three-digit number found that meets the requirements*/
}
for(i=1;i<=j-2;++i) /*Select three of the three digits that meet the conditions and combine them*/
{
b[1]=num[i][0];
b[2]=num[i][1];
b[3]=num[i][2];
for(t=i+1;t<=j-1;++t)
{
b[4]=num[t][0]; /*Take the three-digit number of the t-th number*/
b[5]=num[t][1];
b[6]=num[t][2];
for(flag=0,m=1;!flag&&m<=3;m++) /*flag: A mark with repeated numbers appears*/
for(n=4;!flag&&n<=6;n++) /*Judge whether the numbers of the two numbers are repeated*/
if(b[m]==b[n])flag=1; /*flag=1: The number has duplication*/
if(!flag)
for(k=t+1;k<=j;k++)
{
b[7]=num[k][0]; /*Take the three-digit number of the kth number*/
b[8]=num[k][1];
b[9]=num[k][2];
for(flag=0,m=1;!flag&&m<=6;m++) /*Judge whether the first two numbers are */
for(n=7;!flag&&n<=9;n++) /*Repeat with the number of the third number*/
if(b[m]==b[n])flag=1;
if(!flag) /*If none is repeated, print the result*/
printf("%d,%d,%d\n",a[i],a[t],a[k]);
}
}
}
}
*Run result
The 3 squares with 3 different digits each are:
361,529,784
*Thoughts
Divide nine numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 into two groups. Each number can only be used once. One group forms a 5-digit number and the other group forms a 4-digit number, so that the former is n times the latter. Find all 5-digit and 4-digit numbers that meet the conditions. (Note: It is also impossible for some N whose maximum value is equal to 68,68. Impossible N values include: 1, 10, 11, 20, 21, 25, 30, 31, etc.)
62. A strange cube formed from 8 integers
Give 8 integers arbitrarily, place these 8 integers on the eight vertices of a cube, and require that the sum of the four numbers on each face is equal.
*Problem analysis and algorithm design
Simplify the problem: Convert 8 vertices to the 8 elements in the array, and convert "the sum of the four numbers on each face is equal" into the equality relationship between the sums of the array inequality. The key here is to correctly correspond to the 8 vertices of the cube with the 8 elements of the array.
A simple exhaustive method can be used to create all arrangements of 8 numbers.
*Program description and comments
#include<>
#include<>
int main()
{
int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag;
for(i=1;i<=8;i++) /*Input number*/
{
printf("Please enter [%d]number:",i);
scanf("%d",&a[i]);
ii+=a[i];
}
printf("******************************************\n");
If(ii%2) /*sum is odd, the 8 numbers entered are not available*/
{
printf("Sorry they can't be constructed required cube!\n");
exit(0);
}
for(flag=0,a1=1;a1<=8;a1++) /*flag:Complete mark.flag=1; means completion*/
for(a2=1;a2<=8;a2++) /*Use eight-fold loops to create a full arrangement of eight integers*/
if(a2!=a1) /*The first two numbers cannot be the same*/
for(a3=1;a3<=8;a3++)
if(a3!=a2&&a3!=a1) /*The first three numbers cannot be the same*/
for(a4=1;a4<=8;a4++)
if(a4!=a3&&a4!=a2&&a4!=a1) /*The first four numbers cannot be the same*/
for(b1=1;b1<=8;b1++)
if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1) /*Not the same*/
for(b2=1;b2<=8;b2++)
if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1)
for(b3=1;b3<=8;b3++)
if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1)
/*The same number cannot be taken*/
for(b4=1;b4<=8;b4++)
if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1)
if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2
&&a[a1]+a[a2]+a[b1]+a[b2]==ii/2
&&a[a1]+a[a4]+a[b1]+a[b4]==ii/2)
{
flag=1;goto out; /* If the condition is met, set flag 1 and exit*/
}
out:
if(flag)
{
printf("They can be constructed required cube as follow:\n");
printf(" /%2d…………/%2d\n",a[a4],a[a3]);
printf(" %2d/…………%2d/|\n",a[a1],a[a2]);
printf(" | | | |\n");
printf(" | | | |\n");
printf(" | %2d| | |%2d\n",a[b4],a[b3]);
printf(" /……………./\n");
printf(" %2d/………….%2d/\n",a[b1],a[b2]);
}
else printf("Sorry they can't be constructed required cube!\n");
}
*Run result
Please enter [1] number:20
Please enter [2] number:45
Please enter [3] number:39
Please enter [4] number:25
Please enter [5] number:29
Please enter [6] number:7
Please enter [7] number:3
Please enter [8] number:2
Sorry they can't be constructed required cube!
*Thoughts
The method of establishing a full arrangement in a program is too inefficient. Although the algorithm is simple, the program is too redundant. Please design new algorithms to accomplish the same work by yourself.
63. Reduced restore
Write a program to solve the numbers represented by each letter in the following formula, and different letters represent different numbers.
PEAR
- ARA
——–
PEA
*Problem analysis and algorithm design
Similar problems are relatively simple from the perspective of computer algorithms and can be solved by the most common exhaustive method. The program uses a loop to exhaust the numbers that each letter may represent, and then convert the numbers represented by the letter into corresponding integers. After substituting them into the equation, verifying whether the equation is true to solve the problem.
*Program description and comments
#include<>
int main()
{
int p,e,a,r;
for(p=1;p<=9;p++) /*Exhaust all possible values of the letter p from 1 to 9*/
for(e=0;e<=9;e++) /*All possible values from 0 to exhaustive letter e*/
if(p!=e) /*p does not equal e*/
for(a=1;a<=9;a++) /*Exhaust all possible values of the letter a from 0 to 9*/
if(a!=p&&a!=e)
for(r=0;r<=9;r++) /*Exhaust all possible values of the letter r from 0 to 9*/
if(r!=p&&r!=e&&r!=a&&p*1000+e*100+a*10+r-(a*100+r*10+a)
==p*100+e*10+a)
{
printf(" PEAR %d%d%d%d\n",p,e,a,r);
printf(" -ARA - %d%d%d\n",a,r,a);
printf("…………………….\n");
printf(" PEA %d%d%d\n",p,e,a);
}
}
*Run result
PEAR 1098
- ARA - 989
———- ——
PEA 109
*Thoughts
Please restore the following formula. Different letters represent different numbers.
SEVEN 82524 82526
THREE 19722 19722
+ TWO Answer: + 106 + 104
———- ———– ———–
TWELVE 102352 102352
64. Multiplication restore
A represents the first five numbers in numbers 0 to 9, and Z represents the last five numbers. Please restore the following multiplication formula.
A Z A
× A A Z
————
A A A A
A A Z Z
Z A A
————
Z A Z A A
*Problem analysis and algorithm design
The problem itself is not complicated. You can use exhaustive method for each bit in the multiplication formula to finally get the result. The key to this question is how to effectively judge whether each bit of each part of each meets the question's meaning. If this problem is not handled well, the program written will be very long. A judgment function is used in the program implementation, and all numbers are uniformly judged by the flag string passed into the function.
*Program description and comments
#include<>
void print(long a,long b,long s1,long s2,long s3);
int jud(long q,char *pflag);
int main()
{
long i,j,k,l,m,n,term,t1,t2,t3;
int flag;
for(i=0;i<=4;++i) /*The first digit of the multiplier*/
for(j=5;j<=9;++j) /*The second digit of the multiplier*/
for(k=0;k<=4;++k) /*The third digit of the multiplier*/
{
term=100*i+10*j+k; /*Multiplied*/
for(flag=0,n=0;n<4&&!flag;) /*The first digit of the multiplier*/
flag=jud((t3=++n*100*term)/100,"001"); /*Judge the third part of the product*/
if(flag)
{
for(flag=0,m=0;m<4&&!flag;) /*The second digit of the multiplier*/
flag=jud((t2=++m*10*term)/10,"1100"); /*Judge the second part product*/
if(flag)
{
for(flag=0,l=5;l<9&&!flag;) /*The third digit of the multiplier*/
flag=jud(t1=++l*term,"0000"); /*Judge the first part of the product*/
if(flag&&jud(t1+t2+t3,"00101")) /*Judge product of multiplication*/
print(term,n*100+m*10+l,t1,t2,t3);
}
}
}
}
void print(long a, long b, long s1, long s2, long s3) /*Print result*/
{
printf("\n %ld\n",a);
printf("*) %ld\n",b);
printf("………………….\n");
printf(" %ld\n %ld\n %ld\n",s1,s2/10,s3/100);
printf("………………….\n");
printf(" %ld\n",a*b);
}
int jud(long q,char *pflag) /*The judgment function that determines whether each bit of a number meets the requirements*/
/*q: The number that needs to be judged. pflag: flag string, A is represented by 1, Z is represented by 0. The order of the logo string: ten hundred...*/
{
while(q!=0&&*pflag!=NULL) /*Cycle to determine whether the value range of the corresponding bit is correct*/
if(*pflag-'0'!=(q%10>=5?1:0)) /*Flat bit does not match the corresponding bit, return 0*/
return 0;
else
{
q/=10;++pflag; /*If it matches, take the next one for judgment*/
}
If(q==0&&*pflag==NULL) /*q's digit number is the same as the length of the flag string, return 1*/
return 1;
else return 0;
}
*Run result
3 7 2
× 2 4 6
———-
2 2 3 2
1 4 8 8
7 4 4
————
9 1 5 1 2
*Thoughts
E represents even numbers in numbers 0 to 9, and O represents odd numbers. Please restore the following multiplication formula.
E E O 2 8 5
× O O Answer × 3 9
———– ———–
E O E O 2 5 6 5
E O O 8 5 5
———– ———–
O O O O O 1 1 1 1 5
65. Multiplication Restore (2)
There are multiplication equations as follows:
○○○
× ○○
————
○○○○
○○○○
————
○○○○○
All 18 ○ positions are prime numbers (1, 3, 5 or 7). Please restore this formula.
*Problem analysis and algorithm design
Although there are 18 digits in the problem, the other digits can be determined as long as the multiplier and are multiplied and calculated.
There are 5 digits in total for multiplier and multiplied numbers, and each number is required to be a prime number. It is completely possible to use the exhaustive method to exhaust the multiplier and multiplier, and find the answer after judgment. However, this method gives people the feeling that it is "too stupid", because the numbers composed are only prime numbers (4), and there is no need to exhaust them within such a large range. It is just necessary to test the situation when each digit is a prime number.
The five-fold cycle method is used to achieve exhaustive results for 5 numbers, which have been seen in many previous examples. Loop implementation is simple and easy to use, but there are too many nested levels, and the number of exhaustive variables that directly affects the number of nested layers of the loop. This simple implementation method lacks skill. This example provides another algorithm with the same function. Please read the program for the implementation of this algorithm.
The program does not directly exhaust the prime numbers, but corresponds each prime number to the order of 1 to 4. When exhaustion, only exhaustive processing is performed for 1 to 4. When it is to be determined whether the generated product meets the conditions, an array is used to complete the conversion to the corresponding prime number. Please understand the processing methods in the program. The algorithm used in the program is actually the reciprocity method.
*Program description and comments
#include<>
#define NUM 5 /*Number of variables that need to be exhaustive*/
#define C_NUM 4 /*The range of changes in the value of each variable*/
int a[NUM+1]; /*Array for variables that need to be exhaustive*/
/*a[1]: the hundreds of digits multiplied, a[2]: ten digits, aa[3]: single digits a[4]: ten digits multiplied a[5]: single digits*/
int b[]={0,2,3,5,7}; /*Array of prime numbers, no element 0 is used*/
int f(long sum);
int main()
{
int i,not_finish=1;
i=2; /*i: The pointer subscript of the element to be processed. Set initial value*/
a[1]=1; /*Set the initial value for element 1*/
while(not_finish) /*not_finish: The program runs without ending mark*/
{
while(not_finish&&i<=NUM)
/* Process subsequent elements including the i-th element, and find a possible value method for each variable under the current conditions*/
if(a[i]>=C_NUM) /*When the element to be processed exceeds the specified C_NUM*/
if(i==1&&a[1]==C_NUM)
not_finish=0; /*If element 1 has reached C_NUM, all processing will end*/
else a[i–]=0; /* Set the element to be processed to 0, subscript -1 (return an element)*/
else a[i++]++; /*Add the current element value by adding 1 to the subscript pointer*/
if(not_finish)
{
long int sum1,sum2,sum3,sum4; /*Define temporary variable*/
sum1=b[a[1>*100+b[a[2>*10+b[a[3>; /*calculated multiplier*/
/*Use the corresponding relationship between the subscript of the array and the prime number to complete the conversion of the prime number from 1 to 4 to the prime number*/
sum2=sum1*b[a[5>; /* Calculate the partial product of the multiplier digits and the multiplier*/
sum3=sum1*b[a[4>; /* Calculate the partial product of the multiplier and the multiplier*/
if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3))
/*Judge whether the two-part product meets the question conditions*/
if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4))
/*Judge whether the product of the multiplication meets the question conditions*/
{
printf(" %d\n",sum1); /*If the question is satisfied, print the result*/
printf("* %d%d\n",b[a[4>,b[a[5>);
printf("……………………\n");
printf(" %d\n",sum2);
printf(" %d\n",sum3);
printf("……………………\n");
printf(" %d\n",sum4);
}
i=NUM; /*Preparation for exhaustive next possible value*/
}
}
}
int f(long sum) /*Judge whether each digit of sum is a prime number. If it does not return 0, if it returns 1*/
{
int i,k,flag; /*flag=1: The number is a prime number mark*/
while(sum>0)
{
i=sum%10; /*Take the number of single digits*/
for(flag=0,k=1;!flag&&k<=C_NUM;k++)
if(b[k]==i)
{
flag=1;break;
}
if(!flag) return 0;
else sum=sum/10;
}
return 1;
}
*Run result
7 7 5
× 3 3
———-
2 3 2 5
2 3 2 5
———–
2 5 5 7 5
*Thoughts
In the following multiplication formula, A, B, and C represent a determined number, and ○ represents any number, please restore.
A B C 2 8 6
× B A C × 8 2 6
----- Answer: ----
○○○○ 1 7 1 6
○○A 5 7 2
○○○B 2 2 8 8
————- —————-
○○○○○○ 2 3 6 2 3 6
66. Deformation Restore (1)
Given the following division formula, which contains 5 7s, and the others that are × are any numbers, please restore them.
× 7 × ——————Business
————–
Divider—××|××××————— Divided
×7 7
————–
× 7 ×
× 7 ×
———-
× ×
× ×
———-
○
*Problem analysis and algorithm design
First, analyze the question and deduce as many known conditions as possible from the division itself. It is known from the book of division itself:
1. The range of the dividend is 10000 to 99999, and the range of the dividend is 10 to 99, and it can be divided in an integer manner;
2. The quotient is between 100 and 999, and the ten-digit number is 7;
3. The product of the first digit and the divisor of the quotient is a three-digit number, and the last two digits are 77;
4. The third bit of the dividend must be 4;
5. The product of 7 multiplied by the divisor is a three-digit number, and the second digit is 7;
6. The last digit of the quotient cannot be 0, and the product with the divisor is a two-digit number.
From known conditions, the results can be found using exhaustive methods.
*Program description and comments
#include<>
int main()
{
long int i;
int j,l;
for(i=10000;i<=99999;i++) /*1. i: Divided*/
if(i%1000-i%100==400) /*4. The third bit of the dividend must be 4*/
for(j=10;j<=99;j++) /*1. j: remainder*/
if(i%j==0&&(l=i/j)%100>=70&&l%100<80&&l%10!=0&&l>100&&l<=999)
/*1. Divided && 2. Quotation l is between 100 and 999 and ten digits are 7&&6. The number of quotients cannot be 0*/
if((j*(l%10))<100&&j*(l%10)>10) /*6. The product of the number of quotients and the divisor is a two-digit number*/
if(j*7%100>=70&&j*7%100<80) /*5. The second digit of the product of 7 times the divisor is 7*/
if(j*(l/100)%100==77&&j*(l/100)>100)
/*The last two digits of the product of the first quotient and the divisor are 77*/
printf("%ld/%ld=%d\n",i,j,l);
}
*Run result
51463/53=971。
It can be regarded as the following formula:
9 7 1
————-
5 3| 5 1 4 6 3
4 7 7
————-
3 7 6
3 7 1
———–
5 3
5 3
———–
○
* Further discussion of the problem
Among the known conditions for launch, several of the conditions are very obvious. In other words, the known conditions for launch are to describe the topic in a straightforward manner. This method of deducing known conditions is very simple and effective.
*Thoughts
Only one 8 is given in the following division formula. The other positions where × are marked are any number, please restore.
× 8 × ——————————————
—————-
Divider——-×××| ××××××———— Divided
××××
—————
×××
×××
—————
××××
××××
—————
○
67. Deformation Restore (2)
In the following division formula, only one 7 is given in the quotient. All other positions that hit × are arbitrary numbers, please restore.
×7××× ———————Business
——————
Divider ———————————××××| ×××××××××—————— Divided
×××× ————-1)
—————
××× ————-2)
××× ————-3)
—————
×××× ————-4)
××× ————-5)
—————–
×××× ————-6)
×××× ————-7)
—————–
0
*Problem analysis and algorithm design
This question cannot be solved by a simple exhaustive method. One is that the calculation time is too long, and the other is that it is difficult to find the values of each part of the division formula.
Analyze the division formula and introduce restrictions in multiple places:
From 3) we can see that the second digit of the quotient is multiplied by the divisor by a three-digit number, so the divisor is <=142.
By multiplying the first digit of the divisor to a four-digit number, it can be seen that the first digit of the quotient can only be 8 or 9 and the divisor >=112. At the same time, the fifth quotient is also the first four digits of 8 or 9 must be <=142*9+99 and >=1000+10.
From 4), 5), and 6) it can be seen that the first two digits of 4) must be "10"; the first two digits of 5) must be "9"; the first two digits of 6) must be between 10 and 99; the fourth digit of quotient must be 0.
From the first digit of 5) must be "9" and "112" <= divisor <= 142, we can see that the third digit of the quotient may be 7 or 8.
From the division formula itself, we can see that the fourth quotient is 0.
From 1) we can see that the first digit of the divisor X quotient should be a four-digit number.
From 5) we can see that the third digit of the divisor X quotient should be a three-digit number.
For the sake of convenience when programming, the dividend is decomposed: the first four digits are represented by a[0], the fifth digit is represented by a[1], the sixth digit is represented by a[2], the seventh and eighth digits are represented by a[3]; the divisor is represented by variable b; the decomposition quotient: the first digit is c[0], the fifth digit is represented by c[2]; the other partial quotients are represented by: the first two digits of 2) are d[0], the first three digits of 4) are d[1], and the first two digits of 6) are d[2]. The above analysis can be combined with mathematical methods as:
Divided number: 1010<=a[0]<=1377 0<=a[1]<=9
0<=a[2]<=9 0<=a[3]<=99
Divisor: 112<=b <=142
Quotation: 8<=c[0]<=9 7<=c[1]<=8 8<=c[2]<=9
The first two digits of 2): 10<=d[0]<=99
4) The top three digits: 100<=d[1]<b
The first two digits of 6): 10<=d[2]<=99
1) Partial product of formula: b*c[0]>1000
5) Partial product of formula: 100<b*c[1]<1000
*Program description and comments
#include<>
int main()
{
int a[4],b,c[3],d[4],i=1;
for(a[0]=1010;a[0]<=1377;a[0]++)
for(b=112;b<=142;b++)
for(c[0]=8;c[0]<=9;c[0]++)
if(b*c[0]>1000&&(d[0]=a[0]-b*c[0])>=10&&d[0]<100)
for(a[1]=0;a[1]<=9;a[1]++)
if((d[1]=d[0]*10+a[1]-b*7)>=100&&d[1]<b)
for(a[2]=0;a[2]<=9;a[2]++)
for(c[1]=7;c[1]<=8;c[1]++)
if(b*c[1]<1000&&(d[2]=d[1]*10+a[2]-b*c[1])>=10&&d[2]<100)
for(a[3]=0;a[3]<=99;a[3]++)
for(c[2]=8;c[2]<=9;c[2]++)
if(d[2]*100+a[3]-b*c[2]==0)
{
printf("No%2d:",i++);
printf("%d%d%d%d%d/",a[0],a[1],a[2],a[3]/10,a[3]%10);
printf("%d=",b);
printf("%d%d%d%d%d\n",c[0],7,c[1],0,c[2]);
}
}
*Run result:
No 1:12128316/124=97809
*Thoughts
In the following division formula, all the positions where "×" are located are arbitrary numbers, please restore.
×××××
——————-
××× | ××××××××
××××
——————
××××
×××
—————
×××
×××
———–
××××
××××
———–
0
68. Nine-digit progressive divisor
Find the nine-digit progressive divisor. The so-called nine-digit progressive divisor is such a number: this number consists of nine numbers 1 to 9, and each number only appears once. The first two digits of these nine digits can be divisible by 2, the first three digits can be divisible by 3... The first N digits can be divisible by N, and the entire nine digits can be divisible by 9.
*Problem analysis and algorithm design
The problem itself can be simplified into an exhaustive problem: as long as you exhaust the various possible values of each digit and judge the exhaustive results according to the requirements of the question, you will definitely get the correct result.
The problem gives the condition of "progressive derivation", which allows us to add conditional judgments to the exhaustive method. In the process of exhaustiveness, after determining the value of the partial bit, it is immediately determined whether the generated part meets the "progressive divisible" condition. If it meets, continue to exhaust the next digit; otherwise the digit just generated is wrong. In this way, the conditional judgment can be introduced into the exhaustive method, which can detect contradictions as early as possible and give up unnecessary exhaustive values as soon as possible, thereby improving the execution efficiency of the program.
In order to achieve the purpose of early detection of contradictions, multiple cycle methods cannot be used to implement exhaustive methods, as the quality of the programmed programs is poor. The algorithms used in the program are no longer exhaustive methods, but reciprocating methods.
*Program description and comments
#include<>
#define NUM 9
int a[NUM+1];
int main()
{
int i,k,flag,not_finish=1;
long sum;
i=1;
/*i: The array element being processed means that the first i-1 element has met the requirements, and the i-th element being processed*/
a[1]=1; /* Set initial value for element a[1]*/
while(not_finish) /*not_finish=1: Processing has not ended*/
{
while(not_finish&&i<=NUM)
{
for(flag=1,k=1;flag&&k<i;k++)
if(a[k]==a[i])flag=0; /*Judge whether the i-th element is repeated with the previous i-1 element*/
for(sum=0,k=1;flag&&k<=i;k++)
{
sum=10*sum+a[k];
if(sum%k)flag=0; /*Judge whether the integer composed of the first k bit can be divided by k*/
}
if(!flag) /*flag=0: means that the i-th position does not meet the requirements, and needs to be reset */
{
if(a[i]==a[i-1]) /*If the value of a[i] has been catching up with a[i-1]*/
{
i-; /* The value of i is reduced by 1, return to process the previous element*/
if(i>1&&a[i]==NUM)
a[i]=1; /*When the value of the i-th position reaches NUM, the value of the i-th position is 1*/
else if(i==1&&a[i]==NUM) /*End when the value of the first bit reaches NUM*/
not_finish=0; /*Set the program end flag*/
else a[i]++; /*The value of the i-th position is taken next, add 1*/
}
else if(a[i]==NUM) a[i]=1;
else a[i]++;
}
else /*The i-th position has met the requirements, and the i-th position is handled*/
if(++i<=NUM) /*i+1 handles the next element, when i is not processed*/
if(a[i-1]==NUM) a[i]=1; /*If the value of i-1 is already NUM, then the value of a[i] is 1*/
else a[i]=a[i-1]+1; /* Otherwise, the initial value of a[i] is the "next" value of a[i-1]*/
}
if(not_finish)
{
printf("\nThe progressire divisiable number is:");
for(k=1;k<=NUM;k++) /*Output calculation result*/
printf("%d",a[k]);
if(a[NUM-1]<NUM) a[NUM-1]++;
else a[NUM-1]=1;
not_finish=0;
printf("\n");
}
}
}
*Run result
The progressire divisible number is: 381654729
*Thoughts
Find the N-bit progressive divisor. Use nine numbers from 1 to 9 to form an N(3<=N<=9) digit number. The composition of the digit number is unlimited, so that the first two digits of the N digit number can be divisible by 2, the first 3 digits can be divisible by 3,..., the first N digit can be divisible by N. Find the N-digit number that satisfies the condition.
69. Magician's card guessing technique (1)
The Magician uses 13 spades in a deck of cards to arrange them in advance and stack them together, with the cards facing down. Say to the audience: I don’t look at cards, I can guess what each card is by just counting. I count loudly. Do you listen, don’t you believe it? You just see. The magician put the number of the top card to 1, flipped it over and was exactly A spade A, put spade A on the table, and then count the remaining cards on the hand from top to bottom in order, with the second number of 1 and 2, put the first card under the card, flipped the second card, which happened to be 2 spades, and also put it on the table, with the third number of 1, 2 and 3, put the first two cards under the card, and then flipped the third card to be exactly 3 spades. This way, all 13 cards are turned out in sequence, and it is accurate. Ask the magician how the original order of cards in his hand was arranged?
*Problem analysis and algorithm design
The question has clearly described the magician’s card-playing process, and we can easily deduce the original card sequence using the reverse push method.
The method of manual backward push is: put 13 empty boxes on the table in a circle, number them in sequence starting from 1, put spades A into box No. 1, count the empty boxes from the next empty box, and when counting the second empty box, put spades 2 into the empty box, and then count the empty boxes from the next empty box, and put 3, 4, 5... in sequence until all 3 cards are placed. Note that non-empty boxes should be skipped when counting and count only empty boxes. The order of the last cards in the box is the order of the original cards in the magician's hand.
This manual method is effective and computers can simulate and solve.
*Program description and comments
#include<>
int a[14];
int main()
{
int i,n,j=1; /*j: Array (box) subscript, initially it is element 1*/
printf("The original order of cards is:");
for(i=1;i<=13;i++) /*i: The serial number of the card to be placed in the box*/
{
n=1;
do{
if(j>13) j=1; /*Because the box forms a circle, j exceeds the last element and points to element 1*/
if(a[j]) j++; /*Skip non-empty boxes and do not count*/
else{ if(n==i) a[j]=i; /*If the i-th empty box is counted, put the card into the empty box*/
j++;n++; /*Count the empty box, the array subscript points to the next box*/
}
}while(n<=i); /*Control empty box count is i*/
}
for(i=1;i<=13;i++) /*Order order of output cards*/
printf("%d ",a[i]);
printf("\n");
}
*Run result
The original order of cards is:1 8 2 5 10 3 12 11 9 4 7 6 13
70. Magician's card guessing technique (2)
The magician performed again. He stacked the hearts and spades together, put the cards face down in his hand, and said to the audience: The top one is A spades, and then put them on the table after turning them open. After that, every two pictures from top to bottom is placed at the bottom, and the third one is for the audience to show, which is Spade 2. After putting it on the table, it counts two pictures and puts them at the bottom, and the third one is for the audience to show, which is Spade 3. If this continues, the order in which the audience sees the cards placed on the table is:
Spades A 2 3 4 5 6 7 8 9 10 J Q K
Heart A 2 3 4 5 6 7 8 9 10 J Q K
Ask the magician what the original order of the cards in his hand?
*Problem analysis and algorithm design
This question can be programmed based on the previous question. The difference lies in the counting method and the number of cards. These do not affect our thinking of solving the problem. You can still obtain the order of cards in the magician's hands according to the reverse deduction method.
*Program description and comments
#include<>
int a[27];
int main()
{
int i,n,j=1;
a[1]=1; /*Initialize the first card*/
printf("The original order of cards is:(r:rad b:block):\n");
for(i=2;i<=26;i++)
{
n=1;
do{
if(j>26) j=1; /*If the last element exceeds the point to element 1*/
if(a[j]) j++; /*Skip non-empty boxes and do not count*/
else{
if(n==3) a[j]=i; /*If you count to the third empty box, put the card into the empty box*/
j++; n++; /*Count the empty box, the array subscript points to the next box*/
}
}while(n<=3); /*Control empty box count is 3*/
}
for(i=1;i<=26;i++) /*Order order of output cards*/
{
printf("%c",a[i]>13? 'r':'b');
printf("%d ",a[i]>13? a[i]-13:a[i]);
if(i==13) printf("\n");
}
printf("\n");
}
*Run result
The original order of cards is:(r:rad b:black):
b1 r6 b10 b2 r12 r3 b3 b11 r9 b4 r7 b12 b5
r4 r13 b6 b13 r11 b7 r5 r1 b8 r8 r10 b9 r2
Hundreds of exquisite explanations for classic, practical and interesting programming of C/C++ language (8)
71. Joseph's Problem
This is a story told by the 17th-century French mathematician Gasper in "The Problem of Numbers": 15 believers and 15 non-confucians were in danger in the deep sea. Half of the people had to be thrown into the sea, so the rest could survive. So they thought of a solution: 30 people formed a circle, and counted in turn from the first person to the ninth person. Every time they counted to the ninth person, they threw him into the sea, and the cycle continued until only 15 people remained. Ask how to arrange the method so that every time you throw yourself into the sea, you are non-confucians.
*Problem analysis and algorithm design
The Joseph problem is not difficult, but there are many solutions; there are many variations in the question. Here is a method of implementation.
The 30 people in the question are in a circle, which inspires us to express it with a circular chain. A structure array can be used to form a circular chain. There are two members in the structure, one is a pointer to the next person to form a ring-shaped chain; the other is a mark of whether the person was thrown into the sea, and one means that he is still on the ship. Starting from the first person, counting people who have not been thrown into the sea, every time they count to 9, the mark in the structure is changed to 0, indicating that the person has been thrown into the sea. This cycle counts until 15 people are thrown into the sea.
*Program description and comments
#include<>
struct node
{
int nextp; /* Pointer to the next person (the next person's array subscript)*/
int no_out; /*The mark of whether it is thrown into the sea. 1: Not thrown into the sea. 0: Has been thrown into the sea*/
}link[31]; /*30 people, element 0 is not used*/
int main()
{
int i,j,k;
printf("The original circle is(+:pagendom,@:christian):\n");
for(i=1;i<=30;i++) /*Initialize the structure array*/
{
link[i].nextp=i+1; /*Pointer point to the next person (array element subscript)*/
link[i].no_out=1; /* flag set to 1, indicating that everyone is on the ship*/
}
link[30].nextp=1; /*The pointer of the 30th person points to the first person to form a ring*/
j=30; /*j: Point to the processed array element, counting from the person pointed to by link[i]*/
for(i=0;i<15;i++) /*i: The number of people who have been thrown into the sea*/
{
for(k=0;;) /*k: The counter that determines who is thrown into the sea*/
if(k<15)
{
j=link[j].nextp; /*Modify the pointer and take down a person*/
k+=link[j].no_out; /* for counting. Because the person who has been thrown into the sea is marked as 0*/
}
else break; /* Count to 15 and stop counting*/
link[j].no_out=0; /* Set the mark 0 to indicate that the person has been thrown into the sea*/
}
for(i=1;i<=30;i++) /*Output result*/
printf("%c",link[i].no_out? '@':'+'); /*+: Throwed down from the sea, @: on the ship*/
printf("\n");
}
*Run result
The original circle is(+:pagandom, @:christian):
+++@@+@+@@@+@+++@@+@@@+++@+@@+
(+" means non-congregation who was thrown into the sea @: the congregation who stayed on the boat)
*Thoughts
There are N children in a circle and number them in turn. The teacher specifies that the number will start from the M-th child, and the child will be removed from the list when the S-th child is reported. Then continue to count from the next child, count to the S-th child and let him be removed, so that all the children are removed. Ask the order of children's delisting.
72. Stamp combination
How many different postage can someone get if he has four 3-cent stamps and three 5-cent stamps?
*Problem analysis and algorithm design
The problem is mathematically analyzed, and the postage composed of stamps of different numbers and face values can be calculated using the following formula:
S=3*i+5*j
where i is the number of stamps with 3 points and j is the number of stamps with 5 points
According to the requirements of the question, 3-point stamps can be 0, 1, 2, 3, and 4 stamps, and 5-point stamps can be 0, 1, 2, and 3. By combining the exhaustive method, the postage price after the combination of these postage tags with different face value and different numbers can be obtained.
*Program description and comments
#include<>
int a[27];
int main()
{
int i,j,k,s,n=0;
for(i=0;i<=4;i++) /*i: Take the number of three-point stamps*/
for(j=0;j<=3;j++) /*j: Take the number of stamps with 5 points*/
{
s=i*3+j*5; /*The calculated face value of the stamp*/
for(k=0;a[k];k++) /*Search for if there is the same postage*/
if(s==a[k])break;
if(!a[k]&&s) /*If the same postage is not found, it will be deposited into the array as required*/
{
a[k]=s; n++;
}
}
printf("%d kinds:",n); /*Output result*/
for(k=0;a[k];k++)
printf("%d ",a[k]);
printf("\n");
}
*Run result
19 kinds: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27
73. The sum can represent 5 positive integers from 1 to 23.
It is known that the sum of five positive integers that are different from each other is 23, and selecting several of the five numbers to represent all natural numbers from 1 to 23. What are these five numbers?
*Problem analysis and algorithm design
From the perspective of computer programming, 23 can be decomposed using the exhaustive method, and then judge whether the five decomposed numbers can represent all integers between 1 and 23.
*Program description and comments
#include<>
int main()
{
int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0; /*f: The decomposed 5 numbers can represent the marks of 1~23*/
printf("There are following possble result:\n");
for(a=1;a<=23;a++) /*Decompose 23 into five numbers: a,b,c,d,e*/
for(b=1+a;b<=23-a;b++)
for(c=1+b;c<=23-a-b;c++)
for(d=1+c;d<=23-a-b-c;d++)
{
f=1;
if((e=23-a-b-c-d)>d)
for(f=0,x=1;x<24&&!f;x++) /*Judge whether 5 numbers can represent 1~23*/
for(f=1,i=0;i<2&&f;i++) /* Exhaust all choices of 5 numbers*/
for(j=0;j<2&&f;j++)
for(k=0;k<2&&f;k++)
for(l=0;l<2&&f;l++)
for(m=0;m<2&&f;m++)
if(x==a*i+b*j+c*k+d*l+e*m) f=0;
if(!f) printf("[%d]: %d %d %d %d %d\n",++count,a,b,c,d,e);
}
}
*Run result
There are following possble result:
[1]: 1 2 3 5 12
[2]: 1 2 3 6 11
[3]: 1 2 3 7 10
[4]: 1 2 4 5 11
[5]: 1 2 4 6 10
[6]: 1 2 4 7 9
74. 4 weights that can weigh 1 to 40 pounds
French mathematician Meziac asked a question in his famous "The Game of Numbers" (1962): a businessman had a weight weighing 40 pounds and accidentally threw the weight into four pieces a day. Later, the merchant claimed that the weight of each piece was a whole pound, and found that these four pieces could be weighed on the balance of any weight between 1 and 40 pounds. How much does these four pieces weigh?
*Problem analysis and algorithm design
This question is the development of the previous question. The condition given in the question is "on the balance", which means that the same weight can be placed on either the left side of the balance or on the right side of the balance. If it is stipulated that heavy objects can only be placed on the left side of the balance, when the balance is balanced, there are:
Weight of weight + sum of weight on the left side = sum of weight on the right side
From this we can obtain:
Weight = sum of weights on the right-weights - sum of weights on the left
When programming, just follow the above formula to make the "right weight sum - left weight sum" represent the entire weight between 1 and 40. What you need to pay attention to in programming is how to use a simple method to indicate whether a weight is on the left side of the balance or on the right side of the balance, or is not used at all.
The following program uses 1, -1 and 0 to represent the above three situations, please be careful to understand.
*Program description and comments
#include<>
#include<>
int main()
{
int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag: mark that satisfies the question*/
printf("The weight is broke up as following 4 pieces:");
for(weight1=1;weight1<=40;weight1++) /*Decompose 40 into 4 parts*/
for(weight2=weight1+1;weight2<=40-weight1;weight2++)
for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)
if((weight4=40-weight1-weight2-weight3)>=weight3)
{
for(flag=1,x=1;x<41&&flag;x++) /*Judge whether you can weigh the entire weight between 1 and 40*/
for(flag=0,d1=1;d1>-2;d1–) /*Put the heavy object to the left of the balance*/
for(d2=1;d2>-2&&!flag;d2–) /*1: The weight is on the right side of the balance*/
for(d3=1;d3>-2&&!flag;d3–) /*0: Do not use this weight*/
for(d4=1;d4>-2&&!flag;d4–) /*-1: The weight is on the left side of the balance*/
if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)
flag=1;
if(flag) printf("%d %d %d %d\n",weight1,weight2,weight3,weight4);
flag=0;
}
}
*Run result
The weight is broke up as following 4 pieces: 1 3 9 27
75.10 Children share candy
Ten children gathered in a circle to divide candy. The teacher gave the first child 10 yuan, the second child 2 yuan, the third child 8 yuan, the fourth child 22 yuan, the fifth child 16 yuan, the sixth child 4 yuan, the seventh child 10 yuan, the eighth child 6 yuan, the ninth child 14 yuan, and the tenth child 20 yuan. Then all the children will give half of the sugar in their hands to the child on the right at the same time; those with odd numbers of candy can ask the teacher for a piece. After several times, do you have the same amount of sugar in your hands? How many pieces of candy do each person have?
*Problem analysis and algorithm design
The sugar-sharing process described in the question is a mechanical repetitive process, and the programming algorithm can be simulated completely according to the described process.
*Program description and comments
#include<>
void print(int s[]);
int judge(int c[]);
int j=0;
int main()
{
static int sweet[10]={10,2,8,22,16,4,10,6,14,20}; /*Initialize array data*/
int i,t[10],l;
printf(" child\n");
printf(" round 1 2 3 4 5 6 7 8 9 10\n");
printf("………………………..\n");
print(sweet); /*Output the number of sugar in each person's hand*/
while(judge(sweet)) /*If the requirements are not met, continue the loop*/
{
for(i=0;i<10;i++) /*Divide the sugar in each person's hand into half*/
if(sweet[i]%2==0) /*If it is an even number, it will be divided directly by half*/
t[i]=sweet[i]=sweet[i]/2;
else /*If it is an odd number, add 1 and then divide half*/
t[i]=sweet[i]=(sweet[i]+1)/2;
for(l=0;l<9;l++) /*Give half of the sugar you have distributed to the child on the right (back)*/
sweet[l+1]=sweet[l+1]+t[l];
sweet[0]+=t[9];
print(sweet); /*Output the current number of sugars in each child*/
}
}
int judge(int c[])
{
int i;
for(i=0;i<10;i++) /*Judge whether the sugar in each child's hands is the same*/
if(c[0]!=c[i]) return 1; /*Not the same return 1*/
return 0;
}
void print(int s[]) /*Output the value of each element in the array*/
{
int k;
printf(" %2d ",j++);
for(k=0;k<10;k++) printf("%4d",s[k]);
printf("\n");
}
76. Xiao Ming buys books
Xiao Ming went to the bookstore with his father during the holidays. He selected six books, and the unit prices of each book were: 3.1, 1.7, 2, 5.3, 0.9 and 7.2 respectively. Unfortunately, Xiao Ming's father only brought more than ten yuan. In order to let Xiao Ming have a happy holiday, his father agreed to buy a book, but he asked Xiao Ming to select several books from the six books, so that the combined unit price is closest to the same as 10. Can you help Xiao Ming solve this problem?
*Problem analysis and algorithm design
By analyzing the meaning of the question, you can simplify the question to: select several sums from six numbers, so that the difference between sum and 10 is minimized.
There are two problems hidden in the question: one is how to select several numbers from six numbers; the other is to find the difference between 10.
Selecting several numbers from six numbers is essentially selecting several numbers from six numbers for combination. There are only two situations in the combination process of each number: either select to participate in the sum, or do not select to participate in the sum. This allows you to use a six-fold cycle to combine all possible cases whether each number participates in the sum.
Regarding finding the difference between 10, it should be noted that the difference means the absolute value of the difference. For example: "9-10=-1" and "11-10=1", but the difference between 9 and 11 and 10 is 1. It would be wrong to think that the difference between "9" and "10 is -1.
*Program description and comments
#include<>
#include<>
int main()
{
int d[6],m,i,j;
long b[63],flag;
float c[6],min,x;
printf("Please enter the prices of 6 books:");
for(i=0;i<6;i++) scanf("%f",&c[i]); /*Input six floating point numbers*/
for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*Create all combinations of six numbers and process*/
for(d[1]=0;d[1]<2;d[1]++) /*i: The difference has the number of min combinations*/
for(d[2]=0;d[2]<2;d[2]++) /*min: The minimum difference between 10*/
for(d[3]=0;d[3]<2;d[3]++) /*d[]: Whether to take the flag of this number when combining*/
for(d[4]=0;d[4]<2;d[4]++)
for(d[5]=0;d[5]<2;d[5]++)
{
for(flag=0,x=0,j=5;j>=0;j–)
/*flag: Use the corresponding decimal bit to represent the sum of the six numbers*/
{
x+=c[j]*d[j]; flag=flag*10+d[j];
}
x=((x-10>0)? x-10:10-x); /*x: The difference between the combined sum and 10*/
if(min<0)
{
min=x; /*process the first calculated difference min*/
b[i++]=flag; /*b[]: Array with the same min flag i: the subscript of the array of b[]*/
}
else if(min-x>-6) /*Treatment of new min*/
{
min=x; b[0]=flag; i=1;
}
else if(fabs((double)x-min)<-6)
b[i++]=flag; /*Treatment of equal min*/
}
for(m=0;m<i;m++) /*Outputs the combination of all the differences between i and 10 and min*/
{
printf("10(+ -)%.2f=",min);
for(flag=b[m],j=0;flag>0;j++,flag/=10)
if(flag%10) /*Restore the flag stored in b[] to a combination of each number*/
if(flag>1) printf("%.2f+",c[j]);
else printf("%.2f\n",c[j]);
}
}
*Run result
Please enter the prices of 6 books:3.1 1.7 2.0 5.3 0.9 7.2
10(+ -)0.10=2.00+0.90+7.20
10(+ -)0.10=1.70+2.00+5.30+0.90
10(+ -)0.10=3.10+1.70+5.30
*Thoughts
It can be seen that the algorithm that can produce all combinations of six numbers in the program is not good, and using six-fold loops to process the program seems not concise enough. More general and optimized algorithms can be designed to produce all combinations.
77. Interesting questions about Posunwa wine sharing
The famous French mathematician Povason studied an interesting mathematical problem in his lunar calendar: someone has 12 pints of beer and wants to pour 6 pints out of it, but he does not have a container of 6 pints, only an 8 pint and a 5 pints of container. How can he pour the beer into two 6 pints?
*Problem analysis and algorithm design
Divide the empty bottles of 12 pints of wine, 8 pints and 5 pints in a bisect, and you can abstract it into solving indefinite equations:
8x-5y=6
The meaning is: pour x times from a 12 pint bottle into an 8 pint bottle, and pour the wine from a 5 pint bottle into an 12 pint bottle, and finally the wine remaining in the 12 pint bottle.
Use a, b, and c to represent bottles of 12 pints, 8 pints and 5 pints to find the integer solution of the indefinite equation. According to the meaning of the indefinite equation, the reverse method is:
a -> b -> c ->a
x y
The rules for pouring wine are as follows:
1) In the order of a -> b -> c -> a;
2) Only after b is empty can it be taken from a
3) C can only pour into a
According to the above rules, the program can be written as follows:
*Program description and comments
#include<>
void getti(int a,int y,int z);
int i; /*The weight required to be distributed in the end*/
int main()
{
int a,y,z;
printf("input Full a,Empty b,c,Get i:"); /*a The capacity of the full bottle y: the capacity of the first empty bottle z: the capacity of the second empty bottle*/
scanf("%d%d%d%d",&a,&y,&z,&i);
getti(a,y,z); /*Press a -> y -> z -> a operation steps*/
getti(a,z,y); /*Press a -> z -> y -> a step*/
}
void getti(int a,int y,int z) /*a: The capacity of the full bottle y: The capacity of the first empty bottle z: The capacity of the second empty bottle*/
{
int b=0,c=0; /* b: The actual weight of the first bottle c: The actual weight of the second bottle*/
printf(" a%d b%d c%d\n %4d%4d%4d\n",a,y,z,a,b,c);
while(a!=i||b!=i&&c!=i) /*When the full bottle!=i or the other two bottles are!=i*/
{
if(!b)
{ a-=y; b=y;} /*If the first bottle is empty, pour the full bottle into the first bottle*/
else if(c==z)
{ a+=z; c=0;} /*If the second bottle is full, pour the second bottle into the full bottle*/
else if(b>z-c) /*If the weight of the first bottle > the remaining space of the second bottle*/
{ b-=(z-c);c=z;} /*The second bottle will be filled, and the remaining part will be retained in the first bottle*/
else{ c+=b; b=0;} /* Otherwise, pour all the first bottle into the second bottle*/
printf(" %4d %4d %4d\n",a,b,c);
}
}
*Thoughts
The above program only gives two methods of distributing wine, but no all methods are found. Please design a new algorithm to find all the methods of dividing wine, and find a method with the least amount of wine poured.
78. Find the approximate value of π
Please use the "regular polygon approximation" method to find the approximation of π
*Problem analysis and algorithm design
Using the method of "regular polygon approximation" to find that the π value existed a long time ago. Our ancestors and ancestors used this method to obtain the π value with an accuracy of 6th place after the decimal point in the world.
Use the characteristic that the edge length of a regular hexagon in the circle is equal to the radius to double the edge number, make a regular dodecagon, calculate the edge length, and repeat this process to obtain an approximation of π of the required accuracy.
Assuming that the edge length of the polygon in the unit circle is 2b and the edge number is i, then the edge length of the new regular polygon after the edge number is doubled is:
x=√──────
2-2*√───
1-b*b
──────
2
The circumference is:
y=2 * i * x i: is the number of sides of the regular polygon before doubling
*Program description and comments
#include<>
#include<>
int main()
{
double e=0.1,b=0.5,c,d;
long int i; /*i: number of regular polygon sides*/
for(i=6;;i*=2) /*Double the edge number of regular polygons*/
{
d=1.0-sqrt(1.0-b*b); /* Calculate the side length of the regular polygon in the circle*/
b=0.5*sqrt(b*b+d*d);
if(2*i*b-i*e<1e-15) break; /*The calculation will be stopped if the accuracy reaches 1e-15*/
e=b; /*Save the side length of this regular polygon as the basis for the next precision control*/
}
printf("pai=%.15lf\n",2*i*b); /*Output π value and number of sides of regular polygon*/
printf("The number of edges of required polygon:%ld\n",i);
}
*Run result
pai=3.141592653589794
The number of edges of required polygon:100663296
*Thoughts
Please use the method of tangent regular polygon approximation to find the approximation of π.
79. Find the approximate value of π (2)
Use random number method to find the approximate value of π
*Problem analysis and algorithm design
The idea of finding the approximate value of π by random number method: in a square with unit side length, the side length is the radius and a vertex as the center, and a quarter circle is made on the square of the regime. Randomly throw points into the square, and count if they fall into a quarter circle. Repeat throwing enough points into the square to divide the count falling into a quarter circle by the total number of points, and its value is an approximation of a quarter of the value of π.
You can directly program according to this method. Note: The π value obtained in this method can only be accurate if there are enough statistics.
*Program description and comments
#include<>
#include<>
#include<>
#define N 30000
int main()
{
float x,y;
int c=0,d=0;
randomize();
while(c++<=N)
{
x=random(101); /*x:Coordinates. Generate a total of 101 random numbers between 0 and 100*/
y=random(101); /*y: coordinates. Generate a total of 101 random numbers between 0 and 100*/
if(x*x+y*y<=10000) /*Use the circle equation to determine whether the point falls within the circle*/
d++;
}
printf(" pi=%f\n",4. *d/N); /*Output the calculated π value*/
}
*Run result
Running the program multiple times can result in multiple different counterparts. This is because the approximate values obtained by statistical rules are used. Only when the number of statistics is large enough can the π value be approached. Run four times, the possible results are:
3.122267
3.139733
3.133733
80. An interesting property of odd squares
Programming verification "Odd numbers greater than 1000 have a difference of square and 1 are multiples of 8".
*Problem analysis and algorithm design
This question is an easy-to-prove mathematical theorem, we can write programs to verify it.
The processing process given in the question is very clear, and the algorithm does not require special design. Verification can be performed directly according to the description of the question (only 3000 is verified in the program).
*Program description and comments
#include<>
int main()
{
long int a;
for(a=1001;a<=3000;a+=2)
{
printf("%ld:",a); /*Output odd numbers themselves*/
printf("(%ld*%ld-1)/8",a,a); /*Output (Odd square minus 1)/8*/
printf("=%ld",(a*a-1)/8); /*The output quotient after being divided by 8*/
printf("+%ld\n",(a*a-1)%8); /*Output remainder after being divided by 8*/
}
}
Hundreds of exquisite explanations for classic, practical and interesting programming of C/C++ language (9)
81. Kakuya Guest
A Japanese middle school student discovered a wonderful "theorem" and asked Professor Kakutani to prove it, but the professor was powerless, so he developed Kakutani's conjecture. The conjecture is: give a natural number, if it is an even number divided by 2, if it is an odd number, multiply 3 and add 1, obtain a new natural number and continue to calculate according to the above rules. The result obtained after several times must be 1. Please program verification.
*Problem analysis and algorithm design
This question is a conjecture that has not been obtained in general proof, but it has been tried and proved by the program.
The processing process given in the question is very clear. The algorithm does not require special design and can be directly verified according to the description of the question.
*Program description and comments
#include<>
int main()
{
int n,count=0;
printf("Please enter number:");
scanf("%d",&n); /*Enter any integer*/
do{
if(n%2)
{
n=n*3+1; /*If it is an odd number, n times 3 plus 1*/
printf("[%d]:%d*3+1=%d\n",++count,(n-1)/3,n);
}
else
{
n/=2; /*If it is an even number n divided by 2*/
printf("[%d]: %d/2=%d\n",++count,2*n,n);
}
}while(n!=1); /*n does not equal 1, then continue the above process*/
}
82. Four-way theorem
The famous "Four-Square Theorem" in number theory says that all natural numbers can be expressed as at most by the sum of squares of four numbers.
Please program and verify this theorem.
*Problem analysis and algorithm design
This question is a theorem, we do not prove it but program verification.
The four variables are calculated using a tentative method, and the calculation results are output when they meet the requirements.
*Program description and comments
#include<>
#include<>
int main()
{
int number,i,j,k,l;
printf("Please enter a number=");
scanf("%d",&number); /*Input integer*/
for(i=1;i<number/2;i++) /*Test method. Test the different values of i,j,k,k*/
for(j=0;j<=i;j++)
for(k=0;k<=j;k++)
for(l=0;l<=k;l++)
if(number==i*i+j*j+k*k+l*l) /*If the theorem requirements are met, the result will be output*/
{
printf(" %d=%d*%d+%d*%d+%d*%d+%d*%d\n",number,i,i,j,j,k,k,l,l);
exit(0);
}
}
*Run result
1) Please enter a number = 110
110=7*7+6*6+4*4+3*3
2) Please enter a number = 211
211=8*8+7*7+7*7+7*7
3) Please enter a number = 99
99=7*7+5*5+4*4+3*3
83.Capric constant
Verify the Cabrec operation. For any four-digit number, as long as the numbers on each digit are not the same, there is a rule:
1) Arrange the four numbers that make up the four digits from large to small to form the largest four digit number composed of these four digits;
2) Arrange the four numbers that make up the four digits from small to large to form the smallest four digit number composed of these four digits (if the four numbers contain 0, the resulting number is less than four digits);
3) Find the difference between two numbers and get a new four-digit number (high zero reserved).
Repeat the above process and the final result is 6174, which is called the Cabrec number.
*Problem analysis and algorithm design
The processing process given in the question is very clear. The algorithm does not require special design and can be directly verified according to the description of the question.
*Program description and comments
#include<>
void vr6174(int);
void parse_sort(int num,int *each);
void max_min(int *each,int *max,int *min);
void parse_sort(int num,int *each);
int count=0;
int main()
{
int n;
printf("Enter a number:");
scanf("%d", &n); /*Input any positive integer*/
vr6174(n); /*Calling the function for verification*/
}
void vr6174(int num)
{
int each[4],max,min;
if(num!=6174&&num) /*If it is not equal to 74 and not equal to 0, then perform the Cabrec operation*/
{
parse_sort(num,each); /*Decompose integers and save numbers into each array*/
max_min(each,&max,&min); /*Find the maximum and minimum values of numbers*/
num=max-min; /* Find the difference between the maximum value and the minimum value*/
printf("[%d]: %d-%d=%d\n",++count,max,min,num); /*Output this step of calculation process*/
vr6174(num); /*Recursive call itself continues to perform Cabrec operation*/
}
}
void parse_sort(int num,int *each)
{
int i,*j,*k,temp;
for(i=0;i<=4;i++) /*Decompose NUM into numbers*/
{
j=each+3-i;
*j=num%10;
num/=10;
}
for(i=0;i<3;i++) /*Sort each guarantee number from small to large*/
for(j=each,k=each+1;j<each+3-i;j++,k++)
if(*j>*k) { temp=*j;*j=*k;*k=temp;}
return;
}
void max_min(int *each,int *max,int *min) /*Restore the decomposed number to the maximum integer and the minimum integer*/
{
int *i;
*min=0;
for(i=each;i<each+4;i++) /*Restore to the smallest integer*/
*min=*min*10+*i;
*max=0;
for(i=each+3;i>=each;i-) /*Restore to the largest integer*/
*max=*max*10+*i;
return;
}
*Run result
1) Enter a number:4312
[1]:4312-1234=3078
[2]:8730-378=8352
[3]:8532-2358=6174
2) Enter a number:8720
[1]:8720-278=8442
[2]:8442-2448=5994
[3]:9954-4599=5355
[4]:5553-3555=1998
[5]:9981-1899=8082
[6]:8820-288=8523
[7]:8532-2358=6174
3)Enter a number:9643
[1]:9643-3469=6174
84. Nicoches Theorem
Verify Nicoches' theorem, that is, any cube of an integer can be written as a series of consecutive odd numbers. ××
*Problem analysis and algorithm design
This question is a theorem, let’s first prove that it is valid.
For any positive integer a, whether a is an odd or even number, the integer (a×a-a+1) must be an odd number.
Construct an arithmetic sequence. The first term of the sequence is (a×a-a+1), and the difference of the arithmetic sequence is 2 (odd sequence), then the sum of the previous term a is:
a×((a×a-a+1))+2×a(a-1)/2
=a×a×a-a×a+a+a×a-a
=a×a×a
The theorem holds. Completed the certification.
Through the proof process of the theorem, it can be seen that the first term of the odd number sequence required by L is (a×a-a+1) and the length is a. Programmed algorithms do not require special designs, and can be verified directly according to the proof of the theorem.
*Program description and comments
#include<>
int main()
{
int a,b,c,d;
printf("Please enter a number:");
scanf("%d",&a); /*Input integer*/
b=a*a*a; /*Find the cubic power of an integer*/
printf("%d*%d*%d=%d=",a,a,a,b);
for(d=0,c=0;c<a;c++) /*Output sequence, the first term is a*a-a+1, the arithmetic value is 2*/
{
d+=a*a-a+1+c*2; /*Find the sum of the previous term a of the sequence*/
printf(c?"+%d":"%d",a*a-a+1+c*2);
}
if(d==b)printf(" Y\n"); /*If the condition is satisfied, output "Y"*/
else printf(" N\n"); /* Otherwise output "N"*/
}
*Run result
1) Please enter a number:13
13*13*13=2197=157+159+161+163+165+167+169+171+173+175+177+179+181 Y
2) Please enter a number:14
14*14*14=2744=183+185+187+189+191+193+195+197+199+201+203+205+207+209 Y
*Thoughts
The solution to this problem is to first prove, find the programming algorithm in the process of proof, and then implement programming. In fact, we can also use the commonly used test methods in programming to find the sequence and verify the theorem without proofing. Please design the algorithm yourself. Of course, the sequence obtained in this way may be different from the sequence obtained by the theorem method.
85. The formation of palindrome numbers
Take any decimal integer, add it to the original integer, get a new integer, and repeat the above steps to finally get a palindrome number. Please program verification.
*Problem analysis and algorithm design
This rule of forming palindrome numbers is still a conjecture and has not been proved mathematically. Some palindromes take hundreds of steps to obtain. This is programmed verified here.
The processing process given in the question is very clear, and the algorithm does not require special design. It can be directly verified according to the description of the question.
*Program description and comments
#include<>
#define MAX 2147483647
long re(long int);
int nonres(long int s);
int main()
{
long int n,m;
int count=0;
printf("Please enetr a number optionaly:");
scanf("%ld",&n);
printf("The generation process of palindrome:\n");
while(!nonres((m=re(n))+n)) /*Judge whether an integer and its inverse number are palindrome numbers after adding them*/
{
if(m+n>=MAX)
{
printf(" input error,break.\n");
break;
}
else
{
printf("[%d]:%ld+%ld=%ld\n",++count,n,m,m+n);
n+=m;
}
}
printf("[%d]:%ld+%ld=%ld\n",++count,n,m,m+n); /*Output the last number of palindromes*/
printf("Here we reached the aim at last!\n");
}
long re(long int a) /*Find the inverse number of input integer*/
{
long int t;
for(t=0;a>0;a/=10) /*Inverse the integers*/
t=t*10+a%10;
return t;
}
int nonres(long int s) /*Judge whether the given integer is a palindrome number*/
{
if(re(s)==s) return 1; /*If it is a number of palindromes, return 1*/
else return 0; /* Otherwise return 0*/
}
86. Automatic card deal
There are 52 cards in a deck of poker, and the cards should be distributed to four people when playing bridge. Please design a program to complete the automatic licensing work. Requirements: Spades are represented by S (Spaces); hearts are represented by H (Hearts); squares are represented by D (Diamonds); plum blossoms are represented by C (Clubs).
*Problem analysis and algorithm design
According to the regulations on playing bridge, each person should have 13 cards. When handing out cards, first shuffle the cards, and then send the shuffled cards to each person in a certain order. In order to facilitate computer simulation, the manual card dealing process can be modified: first determine the order of dealing: 1, 2, 3, 4; number the 52 cards in sequence: Spade 2 corresponds to the number 0, Red 2 corresponds to the number 1, Square 2 corresponds to the number 2, Plum Blossom 2 corresponds to the number 3, Spade 3 corresponds to the number 4, Red 3 corresponds to the number 5,... Then draw cards randomly from the 52 cards for each person.
Here we use the random functions of the C library function to generate a total of 52 random numbers between 0 and 51 to produce the effect of reshuffle cards.
*Program and program comments
#include<>
#include<>
int comp(const void *j,const void *i);
void p(int b[],char n[]);
int main(void)
{
static char n[]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
int a[53],b1[13],b2[13],b3[13],b4[13];
int b11=0,b22=0,b33=0,b44=0,t=1,m,flag,i;
while(t<=52) /*Control 52 cards*/
{
m=rand()%52; /*Capplication of random numbers between 0 and 51*/
for(flag=1,i=1;i<=t&&flag;i++)/*Search for if the newly generated random number already exists*/
if(m==a[i]) flag=0; /*flag=1: The generated new random number flag=0: The newly generated random number already exists*/
if(flag)
{
a[t++]=m; /*If a new random number is generated, it will be stored in the array*/
if(t%4==0) b1[b11++]=a[t-1]; /*Judge the current value of t*/
else if(t%4==1) b2[b22++]=a[t-1]; Which array should the card of /* be stored in*/
else if(t%4==2) b3[b33++]=a[t-1];
else if(t%4==3) b4[b44++]=a[t-1];
}
}
qsort(b1,13,sizeof(int),comp); /*Sort each person's cards*/
qsort(b2,13,sizeof(int),comp);
qsort(b3,13,sizeof(int),comp);
qsort(b4,13,sizeof(int),comp);
p(b1,n); p(b2,n); p(b3,n); p(b4,n); /*Print each person's cards separately*/
return 0;
}
void p(int b[],char n[])
{
int i;
printf("\n\006 "); /*Print spade mark*/
for(i=0;i<13;i++) /*Convert the value in the array to the corresponding suit*/
if(b[i]/13==0) printf("%c ",n[b[i]%13]); /*The card corresponding to this suit*/
printf("\n\003 "); /*Print the red peach mark*/
for(i=0;i<13;i++)
if((b[i]/13)==1) printf("%c ",n[b[i]%13]);
printf("\n\004 "); /*Print square mark*/
for(i=0;i<13;i++)
if(b[i]/13==2) printf("%c ",n[b[i]%13]);
printf("\n\005 "); /*Print the plum blossom mark*/
for(i=0;i<13;i++)
if(b[i]/13==3||b[i]/13==4) printf("%c ",n[b[i]%13]);
printf("\n");
}
int comp(const void *j,const void *i) /*sort call sorting function*/
{
return(*(int*)i-*(int*)j);
}
87. Black and white subscription exchange
There are three white and three black spots arranged as shown in the following figure:
○ ○ ○ . ● ● ●
The purpose of the game is to exchange the positions of white and black spots in the above picture with the minimum number of steps:
● ● ● . ○ ○ ○
The rules of the game are: (1) Only one piece can be moved at a time; (2) The piece can be moved into a space, or skipped an opponent's piece into a space, but it cannot jump backwards, nor can it skip two pieces. Please use a computer to implement the above game.
*Problem analysis and algorithm design
The key to solving problems like this is to find out the rules of the problem, or to formulate a set of rules for computer actions. Analyzing this question, first employing people to solve the problem, you can summarize the following rules:
(1) The black spider jumps to the left and falls into the space, turn (5)
(2) White Sword jumps to the right and falls into space, turn (5)
(3) The black piece moves to the left and falls into a space (but the chess piece blocking should not occur), turn (5)
(4) The white piece moves to the right and falls into a space (but the chess piece should not be blocked and cute), turn (5)
(5) Determine whether the game is over. If it is not over, then turn (1) to continue.
The so-called "blocking" phenomenon is that during the process of moving the chess pieces, two chess pieces of the same color that have not yet been in place are connected together, making it impossible for other chess pieces in the chessboard to continue to move. For example, move the chess piece according to the following method:
0
○ ○ ○ . ● ● ●
1 ○ ○ . ○ ● ● ●
2 △ ○ ○ ● ○ . ● ●
3
○ ○ ● . ○ ● ●
4 Two ● are connected together to create blockage
○ ○ ● ● ○ . ●
Or 4 two whites are connected together to create blockage
○ . ● ○ ○ ● ●
The reason for the blockage is that in step 2 (△ state), the chess piece ○ cannot move to the right, but can only move ● to the left.
To summarize the reasons for blockage, when the chessboard appears in "black, white, empty, black" or "white, empty, black, white", the chess piece in the middle cannot be moved left or right, and only the chess piece on both sides.
According to the above rules, it can be ensured that the chess piece cannot move during the process of moving the piece, and the position exchange between the white piece and the black piece can be completed with the minimum number of steps.
*Program description and comments
#include<>
int number;
void print(int a[]);
void change(int *n,int *m);
int main()
{
int t[7]={1,1,1,0,2,2,2}; /*Initialize array 1: white sub 2: black sub 0: space*/
int i,flag;
print(t);
while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=3) /*Judge whether the game is over?
If the exchange of chess pieces has not been completed, the loop continues*/
{
flag=1; /*flag mark for moving one step for the chess piece 1: The chess piece has not been moved 0: The chess piece has been moved*/
for(i=0;flag&&i<5;i++) /*If the white zi can skip the black zi to the right, the white zi will jump to the right*/
if(t[i]==1&&t[i+1]==2&&t[i+2]==0)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<5;i++) /*If the blackspot can jump over the whitespot to the left, the blackspot will jump to the left*/
if(t[i]==0&&t[i+1]==1&&t[i+2]==2)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<6;i++) /*If you move the white sub to the right, it will not cause blockage, then the white sub to the right*/
if(t[i]==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2]))
{change(&t[i],&t[i+1]); print(t);flag=0;}
for(i=0;flag&&i<6;i++) /*If moving the blackspot to the left will not cause blockage, the blackspot will move to the left*/
if(t[i]==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2]))
{ change(&t[i],&t[i+1]); print(t);flag=0;}
}
}
void print(int a[])
{
int i;
printf("No. %2d:………………………..\n",number++);
printf(" ");
for(i=0;i<=6;i++)
printf(" | %c",a[i]==1?'*':(a[i]==2?'@':' '));
printf(" |\n ………………………..\n\n");
}
void change(int *n,int *m)
{
int term;
term=*n; *n=*m; *m=term;
}
* Further discussion of the problem
The rules in this question not only apply to the situation of three chess pieces, but can also be generalized and apply to the situation of any N chess pieces. Readers can programmatically verify that the number of move steps of the chess piece obtained according to this rule is the smallest.
In fact, making rules is the key to solving such problems. A game program "The level of thinking depends entirely on the quality of the rules of use."
*Thoughts
There are two white and two black spots arranged as shown in the left picture:
○ . ○
. . .
● . ●
The chess pieces in the chessboard walk according to the "horse steps" rule, requiring the minimum number of steps to exchange the positions of the white and black pieces in the figure. The final result is shown in the following figure.
● . ●
. . .
○ . ○
88. The ever-winning general
There are 21 matches, and two people take turns to take them. Each person can take 1 to 4 matches each time. They cannot take more, nor can they not take no matter who takes the last match. Whoever takes the last match will lose. Please write a program to play a human-computer game, requiring the human to take it first and the computer to take it later; the computer side is the "eternal victory general".
*Problem analysis and algorithm design
When the computer is behind, in order to make the computer a "ever-winning general", it is necessary to find the key. According to the requirements of this question, the sum of the number of children taken by one party after another and the number of children taken by the other party just took by one step is equal to that, so the last son is guaranteed to be left to the person who took the son first.
Based on this analysis, algorithm design is very simple, and programming is also very easy.
*Program description and comments
#include<>
int main()
{
int a=21,i;
printf("Game begin:\n");
while(a>0)
{
do{
printf("How many stick do you wish to take(1~%d)?",a>4?4:a);
scanf("%d",&i);
}while(i>4||i<1||i>a); /*Receive the exact input*/
if(a-i>0) printf(" %d stick left in the pile.\n",a-i);
if((a-i)<=0)
{
printf(" You have taken the last stick.\n");
printf(" * * * You lose! \nGame Over.\n"); /*Output win mark*/
break;
}
else
printf(" Compute take %d stick.\n",5-i); /*Output the number of subs taken by the computer*/
a-=5;
printf(" %d stick left in the pile.\n",a);
}
}
*Thoughts
If the number of matches in the question is changed (such as 22), the side that goes back may not be able to maintain constant victory, and may change to "often defeat". At this time, the winner of the next side is directly related to the initial number of matches and the maximum number of matches allowed to be taken each time. Please write a program to solve this problem.
89. Grab 30
This is a game among Chinese folks. Two people start to report numbers in turn from 1, each person can report one number or two consecutive numbers at a time. Whoever reports 30 first will be the winner.
*Problem analysis and algorithm design
This question is similar to the previous question, and the algorithm is also similar. The difference is that the first step is optional. If the computer takes the first step, then the computer must be the winner. If a person takes one step first, the computer has to wait for the person to make mistakes. If a person takes the first step first and does not make mistakes, the person will win; otherwise the computer will seize a mistake in a person and make itself a winner.
*Program description and comments
#include<>
#include<>
#include<>
int input(int t);
int copu(int s);
int main()
{
int tol=0;
printf("\n* * * * * * * *catch thirty* * * * * * * \n");
printf("Game Begin\n");
randomize(); /*Initialize the random number generator*/
if(random(2)==1) /*Take a random number to determine which machine or person takes the first step*/
tol=input(tol); /*If it is 1, then Yu Yuan will take the first step*/
while(tol!=30) /*Game end condition*/
if((tol=copu(tol))==30) /*The computer takes a number, if it is 30, the machine will win*/
printf("I lose! \n");
else
if((tol=input(tol))==30) /*People take a number, if it is 30, the person will win*/
printf("I lose! \n");
printf(" * * * * * * * *Game Over * * * * * * * *\n");
}
int input(int t)
{
int a;
do{
printf("Please count:");
scanf("%d",&a);
if(a>2||a<1||t+a>30)
printf("Error input,again!");
else
printf("You count:%d\n",t+a);
}while(a>2||a<1||t+a>30);
return t+a; /*Return the current accumulated sum of the number that has been taken*/
}
int copu(int s)
{
int c;
printf("Computer count:");
if((s+1)%3==0) /*If the modulus of the remaining number is 1, then take 1*/
printf(" %d\n",++s);
else if((s+2)%3==0)
{
s+=2; /*If the modulus of the remaining number is 2, then take 2*/
printf(" %d\n",s);
}
else
{
c=random(2)+1; /* Otherwise, you will randomly take 1 or 2*/
s+=c;
printf(" %d\n",s);
}
return s;
}
*Thoughts
Take a clever even number. There are 25 chess pieces on the table. Both sides take turns to take the pieces. Each person takes at least one chess piece at a time, and up to 3 chess pieces can be taken away. Both sides took it like this until they took all the pieces. Therefore, one side in the hands of both parties must be an even number, the other side is an odd number, and the even number is the winner. Please program and implement human-computer games.
90.Moving Mountain Game
There are n mountains, and both sides of computer and human competition take turns to move the mountains. It is stipulated that the number of mountains moved each time cannot exceed K, and whoever moves the last one will lose. At the beginning of the game. The computer asks people to enter the total number of mountains (n) and the maximum number of mountains allowed to move each time (k). Then ask someone to start. After someone enters the number of mountains that need to be moved, the computer immediately prints out how many mountains it moves and prompts how many mountains it has remained. Both sides took turns moving the mountain until the last mountain was moved. The computer will show who the winner is and ask if the person wants to continue the game. If people don’t want to play anymore, the computer will count how many games they played and how they won or lost.
*Problem analysis and algorithm design
The following principles should be followed when participating in games:
1) When:
The number of remaining mountains -1 <= The maximum number of movable k is to be moved (the number of remaining mountains -1) so that the last mountain is left to people.
2) For any positive integer x, y, there must be:
0<=x%(y+1)<=y
In the case of n mountains, in order to leave the last mountain for people, the computer must control that the number of mountains should not exceed the maximum number k each time it moves, the number of mountains it should move should meet the following relationship:
(n-1)%(k+1)
If the calculation result is 0, that is, there is no remainder, it is stipulated that only 1 mountain will be moved to prevent problems after advancing.
According to this rule, the game program can be written as follows:
#include<>
int main()
{
int n,k,x,y,cc,pc,g;
printf("More Mountain Game\n");
printf("Game Begin\n");
pc=cc=0;
g=1;
for(;;)
{
printf("No.%2d game \n",g++);
printf("—————————————\n");
printf("How many mpuntains are there?");
scanf("%d",&n);
if(!n) break;
printf("How many mountains are allowed to each time?");
do{
scanf("%d",&k);
if(k>n||k<1) printf("Repeat again!\n");
}while(k>n||k<1);
do{
printf("How many mountains do you wish movw away?");
scanf("%d",&x);
if(x<1||x>k||x>n) /*Judge whether the number of mountains to move meets the requirements*/
{
printf("IIIegal,again please!\n");
continue;
}
n-=x;
printf("There are %d mountains left now.\n",n);
if(!n)
{
printf("……………I win. You are failure……………\n\n");cc++;
}
else
{
y=(n-1)%(k+1); /* Find the best number of mountain moving*/
if(!y) y=1;
n-=y;
printf("Copmputer move %d mountains away.\n",y);
if(n) printf(" There are %d mountains left now.\n",n);
else
{
printf("……………I am failure. You win………………\n\n");
pc++;
}
}
}while(n);
}
printf("Games in total have been played %d.\n",cc+pc);
printf("You score is win %d,lose %d.\n",pc,cc);
printf("My score is win %d,lose %d.\n",cc,pc);
}
*Thoughts
A game of picking stones. Divide the stones into several piles, each pile has several grains. The two parties A and B who participated in the game took turns to take any stones from any pile, and they could even take them all, but they could only be taken in one pile at a time. Some are not allowed to be taken from this pile, and some are taken from another pile. Whoever takes the last stone will win. Please program for human-computer chess
Hundreds of explanations for classic, practical and interesting programming of C/C++ language (10)
91. Human-computer number guessing game
The computer "think" a four-digit number, and ask someone to guess what the four-digit number is. After a person enters four digits, the computer first determines that several of the four digits are guessed correctly, and that the positions of the correct digits are also correct. The result is displayed and a prompt is given to people, and ask people to guess again until they guess the four digits the computer thinks.
For example: The computer "thinks" a "1234" and asks someone to guess. The possible prompts are as follows:
Integers guessed by people. Computers judge how many numbers are correct and how many positions are correct.
1122 2 1
3344 2 1
3312 3 0
4123 4 0
1243 4 2
1234 4 4
game over
Please program and implement the game. At the end of the game, it shows how many times people use a number.
*Problem analysis and algorithm design
The problem itself is clear. There is no need for a special algorithm to determine whether the numbers at the same position are the same. Just intercept the numbers at the same position and compare them. But when judging how many digits are correct, you should note that what computers think is "1123", and what people guess is "1576", then the correct number is only 1 digit.
Each digit of the number that is thought by the computer in the program is compared with the number that people guess. If two digits are the same, remember the position of the number you guessed so that the digit can only be "same" as the number corresponding to one. When the next digit is intercepted for comparison, it should no longer be compared with the number at the above position to avoid the error situation where the guessed digit is "same" as the multi-digit number in the corresponding number.
*Program description and comments
#include<>
#include<>
#include<>
int main()
{
int stime,a,z,t,i,c,m,g,s,j,k,l[4]; /*j: The correct number of digits k: The correct number of digits*/
long ltime;
ltime=time(NULL); /*l: When the numbers are the same, the correct position of the number that people guess*/
stime=(unsigned int)ltime/2;
srand(stime);
z=random(9999); /*Computer wants a random number*/
printf("I have a number with 4 digits in mind,please guess.\n");
for(c=1;;c++) /*c: guess the number of times counter*/
{
printf("Enter a number with 4 digits:");
scanf("%d",&g); /*Please guess*/
a=z;j=0;k=0;l[0]=l[1]=l[2]=l[3]=0;
for(i=1;i<5;i++) /*i: the i-th digit in the original number. The number one is the first, and the number one is the fourth*/
{
s=g;m=1;
for(t=1;t<5;t++) /*The number that people guess*/
{
if(a%10==s%10) /*If the i-th position is the same as the t-th position that people guess*/
{
if(m&&t!=l[0]&&t!=l[1]&&t!=l[2]&&t!=l[3])
{
j++;m=0;l[j-1]=t; /*If the number at this position is not "same" as other numbers*/
} /*When recording the same number, the position of the number in the guessed number*/
if(i==t) k++; /*If the position is also the same, then the counter k is added to 1*/
}
s/=10;
}
a/=10;
}
printf("You hane correctly guessed %d digits,\n",j);
printf("and correctly guessed %d digits in exact position.\n",k);
if(k==4) break; /*If all the positions are correct, then the person guesses correctly and exits*/
}
printf("Now you have correctly guessed the whole number after %d times.\n",c);
}
Now you have correctly guessed the whole number after 7 times.
*Thoughts
Guess the number game. The computer "thinks" a number and asks someone to guess. The person enters the guessed number. If the guess is correct, the game will end. Otherwise, the computer will give a prompt indicating whether the number people guessed is too large or too small. When a number has been guessed 20 times and has not been guessed, the guesser should stop the power to continue the game and exit from the program.
92. Human-computer number guessing game (2)
Turn the above game (91. Human-computer guessing game) down, ask someone to think of a four-digit integer, the computer will guess, and the person will give the computer a prompt message, and finally see how many times the computer uses to guess a person's "thinking". Please program and implement it.
*Problem analysis and algorithm design
When solving such problems, the computer's thinking process cannot have complete reasoning skills like a human. The key is to turn the process of reasoning and judgment into a mechanical process and find the corresponding rules, otherwise it will be difficult for the computer to complete the reasoning work.
Based on the analysis and understanding of the problem, the problem is simplified and the solution is divided into two steps to complete: first determine the composition of the four-digit numbers, and then determine the arrangement order of the four-digit numbers. The following rules can be listed:
1) Display four 1s, four 2s,..., four 0s respectively, and determine the composition of the four digits.
2) Generate all arrangements of four digits in sequence (switch the positions of all digits in sequence).
3) Process them separately according to the correct number entered by the person and the number of correct positions:
(Note that there is no input at this time, because if the four numbers have been determined, if 3 positions are correct, the position of the fourth number must be correct)
If typing 4: The game ends.
Determine the difference between this input and the last input
If the difference is 2: It means that the previous input must be 0, and the current input is 2. The positions of the two numbers exchanged this time are correct. Just exchange the other two unswaped numbers to end the game.
If the difference is -2: It means that the input in the previous time must be 2, and the input in this time must be 0. It means that the positions of the two numbers that have just been exchanged are wrong. Just restore the two numbers that have been exchanged and exchange the other two unswaped numbers to end the game.
Otherwise: If the correct position number entered this time is <= the correct position number of last time
Then restore the arrangement of the last four-digit numbers and control it to 3)
Otherwise: use the correct number of positions entered this time as the "correct number of positions entered last time", control to 3).
*Program description and comments
#include<>
#include<>
void bhdy(int s,int b);
void prt();
int a[4],flag,count;
int main()
{
int b1,b2,i,j,k=0,p,c;
printf("Game guess your number in mind is # # # #.\n");
for(i=1;i<10&&k<4;i++) /* Display four 1~9 respectively to determine the composition of the four numbers*/
{
printf("No.%d:your number may be:%d%d%d%d\n",++count,i,i,i,i);
printf("How many digits have bad correctly guessed:");
scanf("%d",&p); /*People input contains several digits*/
for(j=0;j<p;j++)
a[k+j]=i; /*a[]: Stores an array of determined numbers*/
k+=p; /*k: The number of determined numbers*/
}
if(k<4) /* Automatically calculate the number of packages in the four digits*/
for(j=k;j<4;j++)
a[j]=0;
i=0;
printf("No.%d:your number may be:%d%d%d%d\n",++count,a[0],a[1],a[2],a[3]);
printf("How many are in exact positions:"); /*Show four digits in sequence*/
scanf("%d",&b1); /*How many digits are there in the input of the person correctly*/
if(b1==4){prt();exit(0);} /*Four digits are correct, print the result. End the game*/
for(flag=1,j=0;j<3&&flag;j++) /*Realize the pairs of four numbers (a[j],a[k] exchange*/
for(k=j+1;k<4&&flag;k++)
if(a[j]!=a[k])
{
c=a[j];a[j]=a[k];a[k]=c; /*Exchange a[j],a[k]*/
printf("No.%d:Your number may be: %d%d%d%d\n",++count,a[0],a[1],a[2],a[3]);
printf("How many are in exact positins:");
scanf("%d",&b2); /*How many positions are correct for input*/
if(b2==4){prt();flag=0;} /*If all are correct, end the game*/
else if(b2-b1==2)bhdy(j,k); /*If the difference between the last time and this time is 2, then exchanging two elements will end*/
else if(b2-b1==-2) /*If the difference between the last time and this time is -2, it means that the exchanged (a[j], a[k]) is wrong
After restoring (a[j], a[k], you can end the game by exchanging two other elements*/
{
c=a[j];a[j]=a[k];a[k]=c;
bhdy(j,k);
}
else if(b2<=b1)
{
c=a[j];a[j]=a[k];a[k]=c; /*Recover the two numbers of exchange*/
}
else b1=b2; /*Other cases, the newly entered location information will be saved as the last location*/
}
if(flag) printf("You input error!\n"); /*The exchange result still has no result, it can only be an error in the information entered by the person*/
}
void prt() /*Print the result, end the game*/
{
printf("Now your number must be %d%d%d%d.\n",a[0],a[1],a[2],a[3]);
printf("Game Over\n");
}
void bhdy(int s,int b)
{
int i,c=0,d[2];
for(i=0;i<4;i++) /*Look for two elements except s and b*/
if(i!=s&&i!=b) d[c++]=i;
i=a[d[1>;a[d[1>=a[d[0>; a[d[0>=i; /*Exchange two elements except a[s] and a[b]*/
prt(); /*Print the result, end the game*/
flag=0;
}
* Running example
Suppose the four-digit number that people think is: 7215
Game Begin
Now guess your number in mind is # # # #.
No.1:your number may be:1111
* Further discussion of the problem
This program has the advantages of clear logical structure and simple and correct algorithms, but it lacks the necessary error protection function when receiving the input information from people. At the same time, in the third step of reasoning, the digital position information and the answers entered by people are not retained every time during the third step of reasoning. In this way, the legality check cannot be carried out for the information entered by people, that is, it is impossible to check whether the input information of people is contradictory; Tongchen cannot make full use of the previous results.
These defects can be improved, but the last problem is difficult to improve, so it is left to everyone to complete.
*Thoughts
"One-stop game". On a 3×3 board, both parties A and B abandon each other, and both parties take turns to put chess pieces on the board. If one of the boards is in a straight line (horizontal, vertical or diagonal), the party wins. Please write this game program to achieve the game between humans and machines. There are three types of results for the game: loss, win or draw.
During the programming process, please first analyze how to win in the competition and find out where the first step is to win.
93. Tower of Hannover
Around the end of the 19th century, an intellectual toy was sold in stores in Europe. There were three poles on a copper plate. The leftmost pole strung from top to bottom, from small to large, with a tower made of 64 discs. The purpose is to move all the discs on the leftmost rod to the right rod, provided that only one disc can be moved at a time, and the large disc is not allowed to be placed on the small disc.
*Problem analysis and algorithm design
This is a famous question, and it is found in almost all textbooks. Since the condition is that only one disk can be moved at a time, and the large disk is not allowed to be placed on the small disk, the number of movements of the 64 disks is:
18，446，744，073，709，551，615
This is an astronomical number, if it is possible to calculate (not output) every microsecond, it will take almost a million years. We can only find solutions to the problem and solve the Tower of Hanoi at a smaller N value, but it is difficult to solve the Tower of Hanoi with a computer.
Analyze the problem and find out the correct algorithm for moving the plate.
First consider the plate under the rod a rather than the top plate on the rod, so the task becomes:
*Move the 63 plates above to the b pole;
*Move the remaining plate on rod a to rod c;
*Move all the dishes on the b rod to the c rod.
To continue this process, we must first complete the work of moving 63 plates, 62 plates, 61 plates...
To describe the algorithm more clearly, a function movedisc(n,a,b,c) can be defined. The function of this function is to move N plates from rod A to rod B with the help of rod C. In this way, the work of moving N plates can be carried out according to the following process:
1) movedisc(n-1,a,c,b);
2) Move a plate from a to b;
3) movedisc(n-1,c,b,a)；
Repeat the above process until all the dishes are moved into place.
*Program description and comments
#include<>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
int main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",&n); /*Input N value*/
printf("\tneedle:\ta\t b\t c\n");
movedisc(n,'a','c','b'); /*Move N plates from A with the help of B*/
printf("\t Total: %d\n",i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n>0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*Move N-1 plates from fromneedle with toneedle*/
++i;
switch(fromneedle) /*Move a plate on fromneedle to toneedle*/
{
case 'a': switch(toneedle)
{
case 'b': printf("\t[%d]:\t%2d………>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t%2d……………>%2d\n",i,n,n);
break;
}
break;
case 'b': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<……………>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t %2d……..>%2d\n",i,n,n);
break;
}
break;
case 'c': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<…………%2d\n",i,n,n);
break;
case 'b': printf("\t[%d]:\t%2d<……..%2d\n",i,n,n);
break;
}
break;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*Move N-1 plates to toneedle with the help of fromneedle*/
}
}
94. Childbirth
Once upon a time, there was a pair of longevity children. They gave birth to a pair of children every month. The newborn children grew up in two months, and began to give birth to their next generation children at the end of the second month. In this way, generations were born from generation to generation to solve the number of children.
*Problem analysis and algorithm design
The problem can be abstracted into the following mathematical formula:
Un=Un-1+Un-2
in:
n is the number of terms (n>=3). It is the famous Fibonacci odd sequence, the first few of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21…
Phibona odd numbers can be processed in a program in a variety of ways. According to its general recursive formula, the most basic cycle control can be used to achieve the requirements of the question.
*Program description and comments
#include<>
int main()
{
int n,i,un1,un2,un;
for(n=2;n<3;)
{
printf("Please enter required number of generation:");
scanf("%d",&n);
if(n<3) printf("\n Enter error!\n"); /*Control the correct N value*/
}
un=un2=1;
printf("The repid increase of rabbits in first %d generation is as felow:\n",n);
printf("l\tl\t");
for(i=3;i<=n;i++)
{
un1=un2;
un2=un;
un=un1+un2; /*Use the general term formula to solve the value of N term*/
printf(i%10?"%d\t":"%d\n",un);
}
printf("\n");
}
*Run result
Please enter required number of generation: 20
The repid increase of rabbits in first 20 generation is as felow:
1 1 2 3 5 8 13 21 34 55
89 144 233 377 610 987 1597 2584 4181 6765
95. Convert Arabic numerals to Roman numerals
Convert Arabic numerals greater than 0 and less than 1000 to Roman numerals. The correspondence between Arabic numerals and Roman numerals is as follows:
1 2 3 4 5 ……
I II III IV V ……
*Problem analysis and algorithm design
The question shows the correspondence between Arabic numerals and Roman numerals. The number conversion in the question is actually a table search translation. That is, decompose the hundreds, ten, and single bits of the integer from the integer in sequence, find the corresponding rows in the table and output the corresponding characters.
*Programming and programming
#include<>
int main()
{
static char *a[][10]={"","I","II","III","IV","V","VI","VII","VIII","IX"
"","X","XX","XXX","XL","L","LX","LXX","LXXX","XCC",
"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"
}; /*Create a comparison table*/
int n,t,i,m;
printf("Please enter number:");
scanf("%d",&n); /*Input integer*/
printf("%d=",n);
for(m=0,i=1000;m<3;m++,i/=10)
{
t=(n%i)/(i/10); /*Pick the numbers of each bit in sequence from the high to the low bit*/
printf("%s",a[2-m][t]); /*Translation output through the comparison table*/
}
printf("\n");
}
*Run result
1. Please enter number:863
863=DCCCLXIII
2. Please enter number: 256
256=CCLVI
3. Please enter number:355
355=CCCLV
4. Please enter number:522
522=DXXII
5. Please enter number:15
15=XV
*Thoughts
Enter a positive integer N, generate the corresponding English numeric string and output it, for example:
1 ONE 2 TWO 3 THREE
10 TEN 11 ELEVEN
135 ONE HUNDRED THIRTY FIVE
96. Beauty pageant
At the semi-final match of the beauty pageant Grand Prix, a group of players participated in the competition. The rule of the competition was that the higher the final score, the lower the ranking. When the semi-decisions are over, the final score and final ranking must be announced on the spot in the order of the players' appearance. The players who get the same score have the same ranking and the rankings are numbered continuously, and the number of players with the same ranking is not necessary. For example:
Player serial number: 1, 2, 3, 4, 5, 6, 7
Player scores: 5, 3, 4, 7, 3, 5, 6
Then the output rankings are: 3, 1, 2, 5, 1, 3, 4
Please help the Grand Prix Organizing Committee complete the rating and ranking of the semi-finals.
*Problem analysis and algorithm design
If the problem is expressed in programming language, it is to number the integers in array A continuously from small to large, requiring no change of the order of elements in the array, and the same integers must have the same number.
Ordinary sorting methods all need to change the original order of array elements, which obviously cannot meet the requirements. To this end, an array is introduced that specifically stores rankings, and then the usual algorithm is used: find the minimum value among elements that have not yet been ranked, and process elements with the same value, and repeat this process until all elements are arranged.
*Program description and comments
#include<>
#define NUM 7 /*Define the number of people to be processed*/
int a[NUM+1]={0,5,3,4,7,3,5,6}; /* is to simply define the score of the player directly*/
int m[NUM+1],l[NUM+1]; /*m:Array of tags with compiled ranking l:Record subscript of elements of the same ranking */
int main()
{
int i,smallest,num,k,j;
num=1; /*rank*/
for(i=1;i<=NUM;i++) /*Control scanning the entire array, processing one ranking at a time*/
if(m[i]==0) /*If the ranking process has not been performed yet (that is, the first element that has not been processed has been found)*/
{
smallest=a[i]; /*Take the first unprocessed element as the current minimum value*/
k=1; /*Subscript of array l, number of people with the same name*/
l[k]=i; /*Record the subscript of the same name element with smallest score*/
for(j=i+1;j<=NUM;j++) /*From the next element, process the remaining elements*/
if(m[j]==0) /*If it is an element that has not been processed yet*/
if(a[j]<smallest) /*The fraction is less than the current minimum value*/
{
smallest=a[j]; /*, reset the minimum value*/
k=0; /*Reset the number of people with the same name*/
l[++k]=j; /*Record the subscript of the same name element*/
}
else if(a[j]==smallest) /*If the current minimum score is the same*/
l[++k]=j; /*Record element subscripts with the same name*/
for(j=1;j<=k;j++) /*Trade the elements with the same name*/
m[l[j>=num;
num++; /*Add 1*/
i=0; /*Control restart and find the next element that is not ranked*/
}
printf("Player-No score Rank\n");
for(j=1;j<=NUM;j++) /*Control output*/
printf(" %3d %4d %4d\n",j,a[j],m[j]);
}
*Run result
Player-No Score Rank
1 5 3
2 3 1
3 4 2
5 7 5
5 3 1
3 5 3
7 6 4
*Thoughts
If you change the "number of players with the same ranking in the original title, you do not need to consider the number of players with the same ranking" to "number the players' ranking according to the number of players with the same ranking", then how should you modify the program?
97. Sequences that meet specific conditions
Enter m and n (20>=m>=n>0) to find the positive integer sequence i1,i2,…,in that satisfies the following equation, such that: i1+i1+…+in=m, and i1>=i2…>=in. For example:
When n=4, m=8, the following 5 sequences will be obtained:
5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2
*Problem analysis and algorithm design
The original question can be abstracted as: decompose M into N integers, and the sum of N integers is M, i1>=i2>=…>=in. The method of decomposing integers is very low. Since the question contains "i1>=i2>=…..>=in, we can first determine that the value of the rightmost in element is 1, and then according to the conditions, the value of the previous element must be greater than or equal to the value of the current element, and constantly push forward can solve the problem. The following program allows the user to select M and N and output all sequences that meet the conditions.
*Program description and comments
#include<>
#define NUM 10 /*Maximum number of elements allowed to decompose*/
int i[NUM]; /*Array of decomposed values*/
int main()
{
int sum,n,total,k,flag,count=0;
printf("Please enter requried terms(<=10):");
scanf("%d",&n);
printf(" their sum:");
scanf("%d",&total);
sum=0; /*The sum of k elements from back to front*/
k=n; /*The element subscript being processed from back to forward*/
i[n]=1; /*Set the value of the last element to 1 as the initial value*/
printf("There are following possible series:\n");
while(1)
{
if(sum+i[k]<total) /*If the sum of the k bits afterwards is less than the specified total*/
if(k<=1) /*If the first element is about to be processed*/
{i[1]=total-sum;flag=1;} /* calculates the juxtaposition mark of the first element*/
else{
sum+=i[k–];
i[k]=i[k+1]; /* After setting the value of kth bit, k-1*/
continue; /*Continue to process other elements forward*/
}
else if(sum+i[k]>total||k!=1) /*If the sum has exceeded total or is not the first element*/
{ sum-=i[++k]; flag=0;} /*k falls backwards an element*/
else flag=1; /*sum+i[k]=total&&k=1 Then set the flag flag*/
if(flag)
{
printf("[%d]:",++count);
for(flag=1;flag<=n;++flag)
printf("%d",i[flag]);
printf("\n");
}
if(++k>n) /*k After returning an element backward, determine whether the last element has been exited*/
break;
sum-=i[k];
i[k]++; /*Experience the next decomposition*/
}
}
*Run result
Please enter requried terms(<=10):4
their sum:8
There are following possible series:
[1]: 5111
[2]: 4211
[3]: 3311
[4]: 3221
[5]: 2222
98. The Eight Queens Problem
On an 8×8 chessboard, there are 8 queens, each of which takes up one square; the queens are required to "attack" each other, that is, there cannot be two queens in the same row, the same column or the same diagonal line. Ask how many different methods are there.
*Problem analysis and algorithm design
This is an ancient and representative problem, and there are many algorithms when solving it using computers. Only one is introduced here.
Use one-dimensional arrays for processing. The subscript i of the array represents the i-th column on the board, and the value of a[i] represents the position where the queen is placed in the i-th column. For example: a[1]=5 means putting a queen in the fifth line of the first example of the chessboard.
In the program, first assume that a[1]=1, which means that the first queen is placed on the first row of the first column of the chessboard, and then tests the possible position of the queen in the second column. After finding the appropriate position, then deal with the subsequent columns. In this way, through repeated tests of each column, you can finally find out the entire placement method of the queen.
The program uses backtracking method, and refer to the program for details of the algorithm.
*Program description and comments
#include<>
#define NUM 8 /*Define the size of the array*/
int a[NUM+1];
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1; /*The element being processed subscript means that the first i-1 element has met the requirements and the i-th element is being processed*/
a[1]=1; /* Assign initial value to the first element of the array*/
printf("The possible configuration of 8 queens are:\n");
while(not_finish) /*not_finish=1: Processing has not ended yet*/
{
while(not_finish&&i<=NUM) /*The processing has not been completed and the NUMth element has not been processed yet*/
{
for(flag=1,k=1;flag&&k<i;k++) /*Judge whether there are multiple queens in the same line*/
if(a[k]==a[i])flag=0;
for(k=1;flag&&k<i;k++) /*Judge whether there are multiple queens in the same diagonal*/
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
if(!flag) /*If there is a contradiction that does not meet the requirements, the i-th element needs to be reset*/
{
if(a[i]==a[i-1]) /*If the value of a[i] has been catching up with the value of a[i-1]*/
{
i-; /*Return to one step and try to deal with the previous element again*/
if(i>1&&a[i]==NUM)
a[i]=1; /* When a[i] is NUM, set the value of a[i] by 1*/
else if(i==1&&a[i]==NUM)
not_finish=0; /*End when the value of the first bit reaches NUM*/
else a[i]++; /*Pick the value of a[i] next value*/
}
else if(a[i]==NUM) a[i]=1;
else a[i]++; /*Pick the value of a[i] next value*/
}
else if(++i<=NUM)
if(a[i-1]==NUM) a[i]=1; /*If the value of the previous element is NUM, a[i]=1*/
else a[i]=a[i-1]+1; /* Otherwise the value of the element is the next value of the previous element*/
}
if(not_finish)
{
++count;
printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count);
for(k=1;k<=NUM;k++) /*Output result*/
printf(" %d",a[k]);
if(a[NUM-1]<NUM) a[NUM-1]++; /*Modify the value of the second last digit*/
else a[NUM-1]=1;
i=NUM-1; /*Start to find the solution to the next sufficient condition*/
}
}
}
*Thoughts
An 8×8 international chess board with a total of 64 grids. Putting up to five queens into the board can control the entire plate, and no matter which square the opponent's chess piece is placed, it will be eaten. Please program
99. Addition of ultra-long positive integers
Please design an algorithm to complete the addition of two super-long positive integers.
*Problem analysis and algorithm design
First, we need to design a data structure to represent an ultra-long positive integer, and then we can design an algorithm.
First, we use a ring chain with header nodes to represent a non-negative super-large integer. If each number starts from the low bit, the numbers composed of every four digits from the first to the fourth, fifth to eighth bits... are placed in the first, second, and... nodes of the linked list in turn. The highest bit less than 4 bits is stored in the last node of the linked list. The value of the header node is specified as -1. For example:
The large integer "587890987654321" can be represented by the following linked list with header node header:
According to this data structure, you can start from two header nodes, add them in sequence in sequence, and then calculate the required carry and substitute them into the following operations. For specific implementation algorithms, please refer to the comments in the program.
*Program description and comments
#include<>
#include<>
#define HUNTHOU 10000
typedef struct node{ int data;
struct node *next;
}NODE; /*Define the linked list structure*/
NODE *insert_after(NODE *u,int num); /*Insert a new NODE after the u node, its value is num*/
NODE *addint(NODE *p,NODE *q); /*Complete the addition operation and return a pointer to the result *p+*q*/
void printint(NODE *s);
NODE *inputint(void);
int main()
{
NODE *s1,*s2,*s;
NODE *inputint(), *addint(), *insert_after();
printf("Enter S1= ");
s1=inputint(); /*Input is added*/
printf("Enter S2= ");
s2=inputint(); /*Input add number*/
printf(" S1="); printint(s1); putchar('\n'); /*Show added*/
printf(" S2="); printint(s2); putchar('\n'); /*Show the add number*/
s=addint(s1,s2); /*Sum*/
printf("S1+S2="); printint(s); putchar('\n'); /*Output result*/
}
NODE *insert_after(NODE *u,int num)
{
NODE *v;
v=(NODE *)malloc(sizeof(NODE)); /*Application for a NODE*/
v->data=num; /*Assignment*/
u->next=v; /*Insert a NODE after the u node*/
return v;
}
NODE *addint(NODE *p,NODE *q) /*Complete the addition operation and return a pointer to the result of *p+*q*/
{
NODE *pp,*qq,*r,*s,*t;
int total,number,carry;
pp=p->next; qq=q->next;
s=(NODE *)malloc(sizeof(NODE)); /*Create a linked list header for storing sum*/
s->data=-1;
t=s; carry=0; /*carry: carry*/
While(pp->data!=-1&&qq->data!=-1) /*None is not the header*/
{
total=pp->data+qq->data+carry; /*Sum of the corresponding bit and the previous carry*/
number=total%HUNTHOU; /*Finish the value of the part stored in the chain */
carry=total/HUNTHOU; /*calculate the carry*/
t=insert_after(t,number); /*Save part and into the s-direction chain*/
pp=pp->next; /*Pick the following adds respectively*/
qq=qq->next;
}
r=(pp->data!=-1)?pp:qq; /*Get the chain pointer that has not yet been completed*/
while(r->data!=-1) /*Train the larger number in the adder*/
{
total=r->data+carry; /*Add to carry*/
number=total%HUNTHOU; /*Finish the value of the part stored in the chain*/
carry=total/HUNTHOU; /*calculate the carry*/
t=insert_after(t,number); /*Save part and into the chain pointed to by s*/
r=r->next; /*Take the following value*/
}
if(carry) t=insert_after(t,1); /*process the last carry*/
t->next=s; /*Completed and linked list*/
return s; /*Returns the structure pointer to the sum*/
}
NODE *inputt(void) /*Input an extra-long positive integer*/
{
NODE *s,*ps,*qs;
struct number {int num;
struct number *np;
}*p,*q;
int i,j,k;
long sum;
char c;
p=NULL; /*Point to the input integer, the chain is the lowest single bit of the integer, and the tail of the chain is the highest bit of the integer*/
while((c=getchar())!='\n') /*Enter integer, receive numbers by character*/
if(c>='0'&&c<='9') /*If it is a number, save it */
{
q=(struct number *)malloc(sizeof(struct number)); /*Apply for space*/
q->num=c-'0'; /*Save a single integer*/
q->np=p; /*Create pointer*/
p=q;
}
s=(NODE *)malloc(sizeof(NODE));
s->data=-1; /*Create a table to find the chain header for extra-long positive integer*/
ps=s;
while(p!=NULL) /*Convert data in the received temporary data link to the required standard form*/
{
sum=0;i=0;k=1;
while(i<4&&p!=NULL) /*Take out the lower four digits*/
{
sum=sum+k*(p->num);
i++; p=p->np; k=k*10;
}
qs=(NODE *)malloc(sizeof(NODE)); /*Application space*/
qs->data=sum; /*Assign value, create a linked list*/
ps->next=qs;
ps=qs;
}
ps->next=s;
return s;
}
void printint(NODE *s)
{
if(s->next->data!=-1) /*If it is not a header, then output */
{
printint(s->next); /*Recursive output*/
if(s->next->next->data==-1)
printf("%d",s->next->data);
else{
int i,k=HUNTHOU;
for(i=1;i<=4;i++,k/=10)
putchar('0'+s->next->data%(k)/(k/10));
}
}
}
*Run result
*Thoughts
100. Digital Movement
At the nine points in the figure, the middle point is empty, and the remaining points are filled with numbers 1 to 8; the position of 1 to 8 is fixed. Then move the other numbers so that 1 to 8 is arranged clockwise from small to large. The movement rule is: you can only move the numbers along the line to blank points.
Please programmatically display the digital movement process.
*Problem analysis and algorithm design
To analyze the conditions in the question, it is necessary to use the middle blank grid to arrange the numbers clockwise, and during the arrangement process, you can only use blank points to move the numbers. The essence of the problem is to regard the 8 grids outside the matrix as a ring, and the 8 numbers are sorted within the ring, which is the same as the limitations required by the question, "the numbers can only be moved along the line to the blank points", so the middle spaces should be used for sorting, so the required sorting algorithm is unique.
Observe the middle point, it is the only point connected to the other 8 points, that is, it is the center point. The center point has the largest space for activity, and it can move in 8 directions. Make full use of the characteristic of the center point is the key to the success of the algorithm design.
After finding the position where 1 is, the correct position of the other numbers is fixed. We can adjust the positions of each number one by one according to the following algorithm starting from the number 2.
*Determine where the number i should be;
*Start from the position where the number i should be, and look backward to find the current position of the number i;
*If the current position of the number i is incorrect, move the number i from its current position (along the connection line) to the middle space, and free the original position; move all elements in front of the existing space backwards; until the position i should be vacant, move it into the middle space again.
Starting from the number 2, you can complete the moving sorting of all numbers.
When programming, the eight grids outside the matrix are regarded as a ring, and the first element of the ring is uncertain. If the algorithm is not designed well, a lot of effort will be spent in the program to deal with the order of elements in the ring. The 3X3 matrix in the question is represented by a one-dimensional array, and the middle element (number 4) is just a space. Another pointer array is designed to specifically record the connection relationship when the eight grids outside the pointer form a ring. Each element of the pointer array records the corresponding element subscripts of the numbers in the ring in sequence in the original array. In this way, the complex ring relationship in the original matrix is represented by the pointer array as a simple linear relationship, thus greatly simplifying the programming design.
*Program description and comments
#include<>
int a[]={0,1,2,5,8,7,6,3}; /*Pointer array. Serialize the subscript of the element forming the ring in the matrix in sequence*/
int b[9]; /* means 3X3 matrix, b[4] is a space*/
int c[9]; /*After determining the position of 1, the pointer array to adjust the ring*/
int count=0; /*Number move step counter*/
int main()
{
int i,j,k,t;
void print();
printf("Please enter original order of digits 1~8:");
for(i=0;i<8;i++)
scanf("%d",&b[a[i>);
/*Sequentially input 8 numbers outside the matrix, the order of matrix elements is controlled by element a[i] of the pointer array*/
printf("The sorting process is as felow:\n");
print();
for(t=-1,j=0;j<8&&t==-1;j++) /*Determine the location of the number 1*/
if(b[a[j>==1) t=j; /*t: record the location of the number 1*/
for(j=0;j<8;j++) /* Adjust the pointer array of the ring, set the position of the number 1 as the head of the ring*/
c[j]=a[(j+t)%8];
for(i=2;i<9;i++) /*Adjust the position of the numbers in sequence starting from 2*/
/*i: The number being processed, the correct position that i should be in the ring is i-1*/
for(j=i-1;j<8;j++) /*Search in sequence from the correct position where i should be*/
if(b[c[j>==i&&j!=i-1) /*If i is not in the correct position*/
{
b[4]=i; /*Move i to the center space*/
b[c[j>=0;print(); /*Empty the original location of i, output */
for(k=j;k!=i-1;k–) /*Transfer the numbers between the space before the correct position of i one piece in sequence*/
{
b[c[k>=b[c[k-1>; /*The number moves backward*/
b[c[k-1>=0;
print();
}
b[c[k>=i; /*Move the middle number i into the correct position*/
b[4]=0; /*Empty the middle space*/
print();
break;
}
else if(b[c[j>==i) break; /*number i in the correct position*/
}
void print(void) /*Output matrix according to format requirements*/
{
int c;
for(c=0;c<9;c++)
if(c%3==2) printf("%2d ",b[c]);
else printf("%2d",b[c]);
printf("—-%2d—-\n",count++);
}
*Run result
* Further discussion of the problem
Obviously, all the above algorithms can solve the problem, but the number of steps to move is not the least.
Pay attention to two problems in the algorithm. First: The position of the number 1 remains unchanged from beginning to end; second: The position is already the correct number under the initial situation. For example, the numbers 5 and 6, according to the algorithm, when moving other numbers, 5 and 6 have to move many times, which obviously takes a lot of steps.
For example, if the number 1 participates in the moving sorting process of other numbers and makes full use of the condition that the initial positions of numbers 5 and 6 are already correct, the moving sorting process can be greatly optimized.
*Thoughts
Please redesign the algorithm and write more optimized programs to minimize the number of steps you move.
Please design and complete the operations of subtraction, multiplication and division of two super-long positive integers
A said: "I saw three people putting white paper on their foreheads and one person putting black paper on their foreheads."
B said: "I saw that the other four people were covered with black paper on their foreheads."
C said: "I saw that one person's forehead was covered with white paper, and the other three people's forehead was covered with black paper."
D said: "I saw that all four people posted white paper on their foreheads."
E said nothing.
Now it is known that people who post black paper on their foreheads are telling lies, and people who post white paper on their foreheads are telling the truth. Ask these five people who have white paper on their foreheads and whose foreheads are black paper?
*Problem analysis and algorithm design
If the variables A, B, C, D, and E represent the color of the paper posted on each person’s forehead, 0 represents black, and 1 represents white. Based on what A, B, C and D said in the question, the following relationship can be summarized:
A says: a&&b+c+d+e==3||!a&&b+c+d+e!=3
B says: b&&a+c+d+e==0||!b&&a+c+d+e!=0
C says: c&&a+b+d+e==1||!c&&a+b+d+e!=1
D says: d&&a+b+c+e==4||!d&&a+b+c+e!=4
Extract all possible situations of the color of the paper on everyone's forehead and substitute it into the above expression for reasoning operations, so that the above expression is "true" is the correct result.
*Program description and comments
#include<>
int main()
{
int a,b,c,d,e;
for(a=0;a<=1;a++) /*Black: 0 White: 1*/
for(b=0;b<=1;b++) /*Exhaust all the possibilities of five people posting paper on their foreheads*/
for(c=0;c<=1;c++)
for(d=0;d<=1;d++)
for(e=0;e<=1;e++)
if((a&&b+c+d+e==3||!a&&b+c+d+e!=3)
&&(b&&a+c+d+e==0||!b&&a+c+d+e!=0)
&&(c&&a+b+d+e==1||!c&&a+b+d+e!=1)
&&(d&&a+b+c+e==4||!d&&a+b+c+e!=4))
{
printf("A is pasted a piece of %s paper on his forehead.\n",
a?"white":"black");
printf("B is pasted a piece of %s paper on his forehead.\n",
b?"white":"black");
printf("C is pasted a piece of %s paper on his forehead.\n",
c?"white":"black");
printf("D is pasted a piece of %s paper on his forehead.\n",
d?"white":"black");
printf("E is pasted a piece of %s paper on his forehead.\n",
e?"white":"black");
}
}
*Run result
A is pasted a paper of black paper on his forehead. (Black)
B is pasted a paper of black paper on his forehead. (Black)
C is pasted a paper of white paper on his forehead. (White)
D is pasted a paper of black paper on his forehead. (Black)
E is pasted a paper of white paper on his forehead. (White)
53.Doctor Mystery’s Problem (1)
The honest tribe and the lying tribe are different ethnic groups from two desert islands. People from the honest tribe always tell the truth, while people from the lying tribe always tell lies. Dr. Miyu is a smart person. He wants to judge which ethnic group the person he meets comes from.
Dr. Myoyu meets three people and knows that they may be from the Honest or Liars. To investigate what tribe these three people are, the doctor asked their questions separately, and here are their conversations:
Ask the first person: "What kind of tribe are you?" and answer: "Two of us are from the honest tribe." The second person said: "Don't talk nonsense, only one of the three of us is from the honest tribe." After hearing the second person's words, "Yes, there is only one honest tribe."
Please judge which tribe they belong to based on his answer.
*Problem analysis and algorithm design
Suppose these three people are A, B, and C respectively. If you lie, its value is 0, and if you are honest, its value is 1. According to the words of the three people in the question, they can be listed separately:
The first person: a&&a+b+c==2||!a&&a+b+c!=2
The second person: b&&a+b+c==1||!b&&a+b+c!=1
The third person: c&&a+b+c==1||!c&&a+b+c!=1
Using exhaustive methods, results can be easily derived.
*Program description and comments
#include<>
int main()
{
int a,b,c;
for(a=0;a<=1;a++) /*Exhaust all the situations of whether everyone is lying or being honest*/
for(b=0;b<=1;b++) /*Ly: 0 Honesty: 1*/
for(c=0;c<=1;c++)
if((a&&a+b+c==2||!a&&a+b+c!=2) /*Judge whether the question is satisfied*/
&&(b&&a+b+c==1||!b&&a+b+c!=1)
&&(c&&a+b+c==1||!c&&a+b+c!=1))
{
printf("A is a %s.\n",a?"honest":"lier"); /*Output judgment result*/
printf("B is a %s.\n",b?"honest":"lier");
printf("C is a %s.\n",c?"honest":"lier");
}
}
*Run result
A is a lier
B is a lier (liars)
C is a lier
*Thoughts
Dr. Myoyu meets four people and knows that they may be from the Honest and Liars. In order to investigate what tribe these four people are, the doctor asked as usual: "What tribe are you from?"
The first person said: "All four of us are from the lie race."
The second person said: "Only one of us is from the lie group."
The third person said: "Two of the four of us are from the lie clan."
The fourth person said: "I am from the honest tribe."
Ask if the fourth person who claims to be the "Honest Clan" is really from the Honest Clan?
(Answer: The fourth person is from the honest clan.)
54. The Problem of Doctor Myth (2)
The two-sided tribe is a new nation on the deserted island. Their characteristics are that they speak real and false and alter true and false. If the first sentence is true, then the second sentence is false; if the first sentence is false, then the second sentence is true, but there is no rule whether the first sentence is true or false.
Dr. Myoyu met three people and knew that they came from three different ethnic groups: the honest, the lie and the two-faced. The three of them stood shoulder to shoulder in front of the doctor.
The doctor asked the person on the left: "What tribe is the person in the middle?", and the person on the left answered: "The honest tribe."
The doctor asked the middle man: "What kind of tribe are you from?", and the middle man replied: "Two-faced tribe."
The doctor asked the person on the right: "What kind of tribe is the person in the middle?", and the person on the right answered: "The person in the liars".
May I ask: Which ethnic group do these three people belong to?
*Problem analysis and algorithm design
This problem is the most basic problem among the two-faced tribe problem, and it is more complicated than the previous problem of only the honest tribe and the lying tribe. When solving the problem, you should use variables to express these three ethnic groups separately.
Let: variable A=1 means: the person on the left is from the honest family (denoted as A in C language);
The variable B=1 means: the person in the middle is from the honest family (represented as B in C);
The variable C=1 means: the person on the right is from the honest family (denoted as C in C);
The variable AA=1 means: the person on the left is a two-faced family (denoted as AA in C language);
The variable BB=1 means: the person in the middle is a two-faced family (represented as BB in C language);
The variable CC=1 means: the person on the right is a two-faced family (represented as CC in C language);
Then the person on the left is a lying clan, which can be expressed as: A!=1 and AA!=1 (not the honest clan and the two-faced clan)
In C language, it is expressed as:!A&&!AA
The person in the middle is a lie group, which can be expressed as: B!=1 and BB!=1
In C language, it is expressed as:!B&&!BB
The person on the right is a lie clan, which can be expressed as: C!=0 and CC!=1
In C language, it is expressed as: !C&&!CC
According to the conditions in the title "Three people come from three ethnic groups", you can list:
a+aa!=2&&b+bb!=2&&c+cc!=2 and a+b+c==1&&aa+bb+cc==1
According to the answer of the person on the left, it can be said that if they are honest tribes, the people in the middle are also honest tribes; if they are not honest tribes, the people in the middle are not honest tribes. The above conditions can be expressed as:
c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&&cc
Join all logical conditions together and use exhaustive methods to solve them. Any variable that makes the above conditions hold at the same time is the answer to the question.
*Program description and comments
#include<>
int main()
{
int a,b,c,aa,bb,cc;
for(a=0;a<=1;a++) /*Exhausted all situations*/
for(b=0;b<=1;b++)
for(c=0;c<=1;c++)
for(aa=0;aa<=1;aa++)
for(bb=0;bb<=1;bb++)
for(cc=0;cc<=1;cc++)
if(a+aa!=2&&b+bb!=2&&c+cc!=2&& /*Judge logical conditions*/
a+b+c==1&&aa+bb+cc==1 &&
(a&&!aa&&b&&!bb||!a&&!b)&&
!b &&
(c&&!b&&!bb||(!c&&!cc)&&(b||bb)||!c&cc))
{
printf("The man stand on left is a %s.\n",
aa?"double–dealer":(a?"honest":"lier"));
printf("The man stand on left is a %s.\n",
bb?"double–dealer":(b?"honest":"lier"));
printf("The man stand on left is a %s.\n",
cc?"double–dealer":(c?"honest":"lier"));
/*Output the final inference result*/
}
}
*Run result
The man stand on left is a double–dealer.
The man stand on center is a lier.
The man stand on right is a honest.
*Thoughts
When Doctor Miyu met three people, he asked the first person: "What tribe are you from?" and answered: "The Honesty Clan." Asked the second person: "What tribe are you from?" and answered: "What tribe are you from?" and answered: "The Lie Clan." The doctor asked the second person: "Is the first person really from the Honesty Clan?" and answered: "Yes." Asked the third person: "What tribe are you from?" and answered: "What tribe are you from?" and answered: "What tribe is the first person?" and answered: "The two-faced clan."
Please determine which ethnic group this person belongs to?
(Answer: The first person is from the honest tribe, the second person is from the two-faced tribe, and the third person is from the lying tribe.)
55. Which doctor is on duty on that day
The hospital has seven doctors A, B, C, D, E, F, and G. Each person has to take turns to work for one day within one week (Monday to Sunday). Now known:
Doctor A is on duty one day later than Doctor C;
Doctor D is on duty two days later than Doctor E;
Doctor B is on duty three days earlier than Doctor G;
Doctor F’s duty day is between Doctor B and C, and it is Thursday;
Please determine which doctor is on duty every day?
*Problem analysis and algorithm design
From the question, the following known conditions can be derived:
*F is on duty on Thursday;
*B duty date is Monday to Wednesday, and G duty is three days later;
*C's duty date is from Friday to Saturday, and one day later is A's duty;
*E will be on duty after two days; E can only be on duty from Monday to Wednesday;
When programming, use the subscripts of array elements to represent Monday to Sunday, and use the values of array elements to represent seven doctors A to F respectively.
*Program description and comments
#include<>
#include<>
int a[8];
char *day[]={"","MONDAY","TUESDAY","WEDNESDAY","THURSDAYT",
"FRIDAY","SATUDAY","SUNDAY"}; /*Create the week table*/
int main()
{
int i,j,t;
a[4]=6; /* Thursday is F on duty*/
for(i=1;i<=3;i++)
{
a[i]=2; /*Suppose the date of B's duty*/
if(!a[i+3]) a[i+3]=7; /*If there is no one on duty after three days, arrange G on duty*/
else{ a[i]=0;continue;} /* Otherwise, the date of B's duty will be constantly correct*/
for(t=1;t<=3;t++) /*Suppose the time of E on duty*/
{
if(!a[t]) a[t]=5; /*If there is no one on duty on that day, E will be on duty*/
else continue;
if(!a[t+2]) a[t+2]=4; /*If E is on duty for two days, it should be D*/
else{ a[t]=0;continue;} /* Otherwise, the date of E on duty is incorrect*/
for(j=5;j<7;j++)
{
if(!a[j]) a[j]=3; /*If there is no one on duty on that day, then arrange C on duty*/
else continue;
if(!a[j+1]) a[j+1]=1; /*No one is on duty for one day after C, then A should be on duty*/
else{ a[j]=0;continue;} /* Otherwise, the A duty date is incorrect*/
for(i=1;i<=7;i++) /*After arrangement, output result*/
printf("Doctor %c is on duty %s.\n",'A'+a[i]-1,day[i]);
exit(0);
}
}
}
}
*Run result
Doctor E is on duty MONDAY. (Monday: E)
Doctor B is on duty TUESDAY. (Tuesday: B)
Doctor D is on duty WEDNESDAY. (Wednesday: D)
Doctor F is on duty THUESDAY. (Thursday: F)
Doctor G is on duty FRIDAY. (Friday: G)
Doctor C is on duty SATURDAY. (Saturday: C)
Doctor A is on duty SUNDAY. (Sunday: A)
*Thoughts
During the solution to this problem, we only considered the situation within one week and did not consider the situation across the week. The condition for "Doctor B is on duty three days earlier than Doctor G" is simply considered to be three days earlier than Doctor G. If you consider cross-week situations, it may occur: Doctor B is on duty on Monday, while Doctor G is on Friday last week. Similarly, the condition that "Doctor F's duty day is between Doctor B and Doctor C" can also be expanded to: "As long as Doctor F's duty day is between Doctor B and Doctor C, it is fine."
Please consider possible schedules where cross-week situations are allowed.
56. Distinguish the nationality of a traveler
There are six people of different nationalities living in a hotel, from the United States, Germany, Britain, France, Russia and Italy. Their names are A, B, C, D, E and F. The order of names does not necessarily correspond to the nationality above. Now known:
1)A Americans are doctors.
2) E and the Russians are technicians.
3) C and Germans are technicians.
4) B and F have served as soldiers, but the Germans have never joined the army.
5) French people are older than A; Italians are older than C.
6) B and Americans will travel to Xi'an next week, while C and French will go to Hangzhou for vacation next week.
Based on the above known conditions, which country are A, B, C, D, E and F from each?
*Problem analysis and algorithm design
First, conduct a question analysis and use known conditions as much as possible to determine who is not from which country.
From: 1) 2) 3) It can be seen that A is not an American, E is not a Russian, and C is not a German. In addition, because A is different from the profession of Germans, E is different from the profession of Americans and Germans, and C is different from the profession of Americans and Russians, so A is not a Russian or German, E is not an American or German, and C is not an American or Russian.
From 4) and 5) we can see that B and F are not Germans, A is not French, and C is not Italian.
From 6) we can see that B is not an American or a Frenchman (because B is different from the French travel location next week); C is not a Frenchman.
Summarize the above results to obtain the following condition matrix:
. American (doctor) British, French, German (technician) Italy Russian (teacher)
A(Doctor) X. X. X. X
B X . X X . .
C (Technician) X. X X X X
D . . . . . .
E(Teacher) X . . X . X
F . . . X . .
According to this table, you can easily get the answer to the question.
It is easy to input the condition matrix into the computer and implement the elimination algorithm with programs.
*Program description and comments
#include<>
char *m[7]={" ","","","FRANCE","GER","ITALI","EUSSIAN"}; /*National name*/
int main()
{
int a[7][7],i,j,t,e,x,y;
for(i=0;i<7;i++) /*Initialization condition matrix*/
for(j=0;j<7;j++) /*Actor, listed as a country, the value of the element indicates that someone is the country*/
a[i][j]=j;
for(i=1;i<7;i++) /*Element 0 of each column of the condition matrix is used as the mark for data processing of this column*/
a[0][i]=1; /*Tag this column has not been processed yet*/
a[1][1]=a[2][1]=a[3][1]=a[5][1]=0; /*Enter various conditions in the condition matrix*/
a[1][3]=a[2][3]=a[3][3]=0; /*0 means that people are not from the country*/
a[1][4]=a[2][4]=a[3][4]=a[5][4]=a[6][4]=0;
a[3][5]=0;
a[1][6]=a[3][6]=a[5][6]=0;
while(a[0][1]+a[0][2]+a[0][3]+a[0][4]+a[0][5]+a[0][6]>0)
{ /*Exit the loop after all six columns are processed*/
for(i=1;i<7;i++) /*i:Column coordinates*/
if(a[0][i]) /*If the column has not been processed yet, then process it*/
{
for(e=0,j=1;j<7;j++) /*j:Line coordinates e:Non-0 element counter in this column*/
if(a[j][i]) { x=j;y=i;e++;}
if(e==1) /*If there is only one element in this column that is non-zero, then perform an elimination operation*/
{
for(t=1;t<7;t++)
if(t!=i)a[x][t]=0; /*Set other elements of the row where the non-zero element is located 0*/
a[0][y]=0; /*Set the flag that has been processed in this column*/
}
}
}
for(i=1;i<7;i++) /*Output inference result*/
{
printf("%c is coming from ",'A'-1+i);
for(j=1;j<7;j++)
if(a[i][j]!=0)
{ printf("%s.\n",m[a[i][j>); break;}
}
}
*Run result
A is coming from ITALY. (Italian)
B is coming from EUSSIAN. (Russian)
C is coming from .. (British)
D is coming from GER. (German)
E is coming from FRANCE. (French)
F is coming from .. (American)
* Further discussion of the problem
Generating a conditional matrix and then using the elimination method for inference judgment is a common method. It is very effective in solving more complex logical problems.
*Thoughts
In the geography class, the teacher gave a map of China without specifying the provinces, and selected five provinces from 1 to 5 numbers, and asked everyone to write the names of the provinces. After handing over the paper, each of the five students only answered the names of two provinces as follows, and each of them only answered one province correctly. What is the correct answer?
A: Shaanxi No. 2, Gansu No. 5 B: Hubei No. 2, Shandong No. 4
C Answer: Shandong No. 1, Jilin No. 5 D Answer: Hubei No. 3, Jilin No. 4
E Answer: Gansu No. 2, Shaanxi No. 3
57. Whose child runs the slowest
The Zhang and Li families each have three children. One day, nine children from the three families competed together for a sprint. Regardless of age, they scored 9 points for the first place, scored 8 points for the second place, and so on. The total scores of each family are the same, and these children do not reach the finish line at the same time, and no two or three children in the family get connected rankings. The children of the Li family were known to be the first place, and the children of the Wang family were the second place. Ask whose child was the last one?
*Problem analysis and algorithm design
According to the conditions of the question, there are 1+2+3+…+9=45 points, and the score of each child should be 15 points. According to the question, we can see that the children of the Li family won the first place, and the children of the Wang family won the second place, so we can say that the children of the Zhang family won the third place must be the children of the Zhang family. From "these children did not reach the finish line at the same time", we can see that the rankings cannot be tied, and from "no family of two or three children get connected rankings" we can see that the fourth place cannot be the child of the Zhang family.
For convenience in the program, it is directly expressed by scores.
*Program description and comments
#include<>
int score[4][4];
int main()
{
int i,j,k,who;
score[1][1]=7; /*Initialize according to known conditions: score[1]: The score of the three children of the Zhang family*/
score[2][1]=8; /*score[2]: The scores of the three children of the Wang family*/
score[3][1]=9; /*The scores of the three children of the Li family*/
for(i=4;i<6;i++) /*i: The possible scores of Zhang's children in the 4 to 6 segments*/
for(j=4;j<7;j++) /*j: Possible scores for Wang's children in segments 4 to 6*/
for(k=4;i!=j&&k<7;k++) /*k: Possible scores for Li's children in the 4 to 6th segment*/
if(k!=i&&k!=j&&15-i-score[1][1]!=15-j-score[2][1] /*Scores cannot be paralleled*/
&&15-i-score[1][1]!=15-k-score[3][1]
&&15-j-score[2][1]!=15-k-score[3][1])
{
score[1][2]=i;score[1][3]=15-i-7; /*Record the result that meets the conditions into the array*/
score[2][2]=j;score[2][3]=15-j-8;
score[3][2]=k;score[3][3]=15-k-9;
}
for(who=0,i=1;i<=3;i++,printf("\n"))
for(j=1;j<=3;j++)
{
printf("%d",score[i][j]); /*Output scores of each child*/
if(score[i][j]==1)who=i; /*Record the family number of the last one*/
}
if(who==1) /*Output the final judgment result*/
printf("The last one arrived to end is a child from family Zhang.\n");
else if(who==2)
printf("The last one arrived to end is a child from family Wang.\n");
else printf("The last one arrived to end is a child from family Li.\n");
}
*Run result
7 5 3
8 6 1
9 4 2
The last one arrived to end is a child from family Wang.
(The last one was the Wang family’s child.
58. Latin square array
Construct the NXN order Latin square matrix (2<=N<=9), so that the numbers 1 to N appear only once in each row and column in the square matrix. If N=4:
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
*Problem analysis and algorithm design
There are many ways to construct Latin square arrays, and here is the easiest method. Observing the example given, it can be found that if the number in the first column and the number in the last column are connected to form a ring, the ring is exactly composed of 1 to N order; for the i-th row, the starting number of this ring is i. According to this rule, it is easy to write a program. The following is a program for constructing a 6th-order Latin square matrix.
*Program description and comments
#include<>
#define N 6 /*Determine N value*/
int main()
{
int i,j,k,t;
printf("The possble Latin Squares of order %d are:\n",N);
for(j=0;j<N;j++) /*Construct N different Latin square matrix*/
{
for(i=0;i<N;i++)
{
t=(i+j)%N; /*Determine the value of the first element in the i-th row of the Latin matrix*/
for(k=0;k<N;k++) /*Output each element in the line in the form of a ring*/
printf("%d",(k+t)%N+1);
printf("\n");
}
printf("\n");
}
}
*Run result
The possble Latin Squares of order 6 are:
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
4 5 6 1 2 3 5 6 1 2 3 4 6 1 2 3 4 5
5 6 1 2 3 4 6 1 2 3 4 5 1 2 3 4 5 6
6 1 2 3 4 5 1 2 3 4 5 6 2 3 4 5 6 1
1 2 3 4 5 6 2 3 4 5 6 1 3 4 5 6 1 2
2 3 4 5 6 1 3 4 5 6 1 2 4 5 6 1 2 3
3 4 5 6 1 2 4 5 6 1 2 3 5 6 1 2 3 4
59.Fill in the form
Fill in the table below 1, 2, 3, 4, 5 and 6 so that the numbers on the right of each column are larger than the numbers on the left, and the numbers on the bottom of each row are larger than the numbers on the top. According to this requirement, how many ways to fill in it?
*Problem analysis and algorithm design
Analysis according to the requirements of the question, the number 1 must be placed in the grid of the first row and the first column, and the number 6 must be placed in the grid of the second row and the third column. In implementation, you can use a one-dimensional array to represent, the first three elements represent the first row and the last three elements represent the second row. First, initialize the array according to the original question, and then test according to the requirements for filling in the numbers in the question.
*Program description and comments
#include<>
int jud1(int s[]);
void print(int u[]);
int count; /*Counter*/
int main()
{
static int a[]={1,2,3,4,5,6}; /*Initialize array*/
printf("The possble table satisfied above conditions are:\n");
for(a[1]=a[0]+1;a[1]<=5;++a[1]) /*a[1] must be greater than a[0]*/
for(a[2]=a[1]+1;a[2]<=5;++a[2]) /*a[2] must be greater than a[1]*/
for(a[3]=a[0]+1;a[3]<=5;++a[3]) /*The a[3] in the second line must be greater than a[0]*/
for(a[4]=a[1]>a[3]?a[1]+1:a[3]+1;a[4]<=5;++a[4])
/*The second row a[4] must be greater than the left side a[3] and the upper side a[1]*/
if(jud1(a)) print(a); /*If the question is satisfied, print the result*/
}
int jud1(int s[])
{
int i,l;
for(l=1;l<4;l++)
for(i=l+1;i<5;++i)
if(s[l]==s[i]) return 0; /*If there are duplicate numbers in the array, return 0*/
return 1; /*If the numbers in the array are not repeated, return 1*/
}
void print(int u[])
{
int k;
printf("\nNo.:%d",++count);
for(k=0;k<6;k++)
if(k%3==0) /*Output the first three elements of the array as the first line*/
printf("\n%d",u[k]);
else /*Output the last three elements of the array as the second line*/
printf("%d",u[k]);
}
*Run result
The possble table satisfied above conditions are:
No.1: No.2: No.3: No.4: No.5:
1 2 3 1 2 4 1 2 5 1 3 4 1 3 5
4 5 6 3 5 6 3 4 6 2 5 6 2 4 6
60.1~9 is divided into three 3-digit numbers of 1:2:3
Divide the nine numbers 1 to 9 into three 3-digit numbers, and find the first 3-digit number, which is exactly twice the second 3-digit number and three times the third 3-digit number. Ask how to divide it.
*Problem analysis and algorithm design
There is a mathematical relationship between the three numbers in the problem. In fact, just determine the first three-digit number to solve the problem.
After testing the first three-digit number, calculate the other two numbers, decompose them into three-digit numbers, and then make a judgment to determine whether the number being tested is the answer.
It should be noted that the initial value of the test can be 123 and the maximum value is 333. Because it is impossible to exceed this range.
*Programming and programming
#include<>
int ok(int t,int *z);
int a[9];
int main()
{
int m,count=0;
for(m=123;m<=333;m++) /*Test possible three-digit numbers*/
if(ok(m,a)&&ok(2*m,a+3)&&ok(3*m,a+6)) /*If the question is satisfied*/
printf("No.%d: %d %d %d %d\n",++count,m,2*m,3*m); /*Output result*/
}
int ok(int t,int *z) /*Decompose the value of t and store it into the three array elements pointed to by z. If the requirements are met, return 1*/
{
int *p1,*p2;
for(p1=z;p1<z+3;p1++)
{
*p1=t%10; /*Decompose integer*/
t/=10;
for(p2=a;p2<p1;p2++) /*Query whether the decomposed number has appeared*/
if(*p1==0||*p2==*p1)return 0; /*If repeated, return */
}
return 1; /* Otherwise return 1*/
}
*Run result
No.1:192 384 576
No.2:219 438 657
No.3:273 546 819
No.4:327 654 981
*Thoughts
Find all possible formulas of the following forms, each formula has nine digits, just using up the nine numbers 1 to 9.
1)○○○+○○○=○○○ (There are 168 possible combinations in total)
2)○×○○○○=○○○○ (There are 2 possible combinations in total)
3)○○×○○○=○○○○ (There are 7 possible combinations in total)
4)○×○○○=○○×○○○ (There are 13 possible combinations in total)
5)○×○○○=○×○○○○○ (There are 28 possible combinations in total)
6)○○×○○=○×○○○○○ (There are 7 possible combinations in total)
7)○○×○○=○○×○○○ (There are 11 possible combinations in total)
Hundreds of exquisite explanations of classic, practical and interesting programming of C/C++ language (7)
61.1~9 constitutes three 3-digit square numbers
Divide nine numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 into three groups. Each number can only be used once, that is, there are no repeated numbers in each group, nor are they repeated with the three numbers in other groups. The three digits in each group are required to form a square number.
*Problem analysis and algorithm design
There are many ideas for this problem, and here is a simple and fast algorithm.
First, find a three-digit number that does not contain 0 and is the square of an integer. There are not many such three-digit numbers. The three-digit numbers that meet the conditions are then combined so that the 9 numbers of the selected three three-digit numbers are not repeated.
The process of finding a three-digit number with a sufficient condition can be combined in the program with the process of digitally decomposing the three-digit number.
*Program description and comments
#include<>
int main()
{
int a[20],num[20][3],b[10]; /*a: Store three-digit numbers that meet the conditions*/
/*If it is not a multiple of 10, then decompose the three-digit number*/
/*Decompose each number in the three digits*/
int i,j,k,m,n,t,flag;
printf("The 3 squares with 3 different digits each are:\n");
for(j=0,i=11;i<=31;i++) /*Finding the three-digit number that is a square number*/
if(i%10!=0) /*If it is not a multiple of 10, then decompose the three-digit number*/
{
k=i*i; /*Decompose each number in the three-digit number*/
num[j+1][0]=k/100; /*Hundred digits*/
num[j+1][1]=k/10%10; /*Ten digits*/
num[j+1][2]=k%10; /*single digit*/
if(!(num[j+1][0]==num[j+1][1]||num[j+1][0]==num[j+1][2]||
num[j+1][1]==num[j+1][2])) /*If the three digits of the decomposition are not equal*/
a[++j]=k; /*j: Counter, counting the three-digit number found that meets the requirements*/
}
for(i=1;i<=j-2;++i) /*Select three of the three digits that meet the conditions and combine them*/
{
b[1]=num[i][0];
b[2]=num[i][1];
b[3]=num[i][2];
for(t=i+1;t<=j-1;++t)
{
b[4]=num[t][0]; /*Take the three-digit number of the t-th number*/
b[5]=num[t][1];
b[6]=num[t][2];
for(flag=0,m=1;!flag&&m<=3;m++) /*flag: A mark with repeated numbers appears*/
for(n=4;!flag&&n<=6;n++) /*Judge whether the numbers of the two numbers are repeated*/
if(b[m]==b[n])flag=1; /*flag=1: The number has duplication*/
if(!flag)
for(k=t+1;k<=j;k++)
{
b[7]=num[k][0]; /*Take the three-digit number of the kth number*/
b[8]=num[k][1];
b[9]=num[k][2];
for(flag=0,m=1;!flag&&m<=6;m++) /*Judge whether the first two numbers are */
for(n=7;!flag&&n<=9;n++) /*Repeat with the number of the third number*/
if(b[m]==b[n])flag=1;
if(!flag) /*If none is repeated, print the result*/
printf("%d,%d,%d\n",a[i],a[t],a[k]);
}
}
}
}
*Run result
The 3 squares with 3 different digits each are:
361,529,784
*Thoughts
Divide nine numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9 into two groups. Each number can only be used once. One group forms a 5-digit number and the other group forms a 4-digit number, so that the former is n times the latter. Find all 5-digit and 4-digit numbers that meet the conditions. (Note: It is also impossible for some N whose maximum value is equal to 68,68. Impossible N values include: 1, 10, 11, 20, 21, 25, 30, 31, etc.)
62. A strange cube formed from 8 integers
Give 8 integers arbitrarily, place these 8 integers on the eight vertices of a cube, and require that the sum of the four numbers on each face is equal.
*Problem analysis and algorithm design
Simplify the problem: Convert 8 vertices to the 8 elements in the array, and convert "the sum of the four numbers on each face is equal" into the equality relationship between the sums of the array inequality. The key here is to correctly correspond to the 8 vertices of the cube with the 8 elements of the array.
A simple exhaustive method can be used to create all arrangements of 8 numbers.
*Program description and comments
#include<>
#include<>
int main()
{
int a[9],ii=0,i,a1,a2,a3,a4,b1,b2,b3,b4,flag;
for(i=1;i<=8;i++) /*Input number*/
{
printf("Please enter [%d]number:",i);
scanf("%d",&a[i]);
ii+=a[i];
}
printf("******************************************\n");
If(ii%2) /*sum is odd, the 8 numbers entered are not available*/
{
printf("Sorry they can't be constructed required cube!\n");
exit(0);
}
for(flag=0,a1=1;a1<=8;a1++) /*flag:Complete mark.flag=1; means completion*/
for(a2=1;a2<=8;a2++) /*Use eight-fold loops to create a full arrangement of eight integers*/
if(a2!=a1) /*The first two numbers cannot be the same*/
for(a3=1;a3<=8;a3++)
if(a3!=a2&&a3!=a1) /*The first three numbers cannot be the same*/
for(a4=1;a4<=8;a4++)
if(a4!=a3&&a4!=a2&&a4!=a1) /*The first four numbers cannot be the same*/
for(b1=1;b1<=8;b1++)
if(b1!=a4&&b1!=a3&&b1!=a2&&b1!=a1) /*Not the same*/
for(b2=1;b2<=8;b2++)
if(b2!=b1&&b2!=a4&&b2!=a3&&b2!=a2&&b2!=a1)
for(b3=1;b3<=8;b3++)
if(b3!=b2&&b3!=b1&&b3!=a4&&b3!=a3&&b3!=a2&&b3!=a1)
/*The same number cannot be taken*/
for(b4=1;b4<=8;b4++)
if(b4!=b2&&b4!=b1&&b4!=b3&&b4!=a4&&b4!=a3&&b4!=a2&&b4!=a1)
if(a[b1]+a[b2]+a[b3]+a[b4]==ii/2
&&a[a1]+a[a2]+a[b1]+a[b2]==ii/2
&&a[a1]+a[a4]+a[b1]+a[b4]==ii/2)
{
flag=1;goto out; /* If the condition is met, set flag 1 and exit*/
}
out:
if(flag)
{
printf("They can be constructed required cube as follow:\n");
printf(" /%2d…………/%2d\n",a[a4],a[a3]);
printf(" %2d/…………%2d/|\n",a[a1],a[a2]);
printf(" | | | |\n");
printf(" | | | |\n");
printf(" | %2d| | |%2d\n",a[b4],a[b3]);
printf(" /……………./\n");
printf(" %2d/………….%2d/\n",a[b1],a[b2]);
}
else printf("Sorry they can't be constructed required cube!\n");
}
*Run result
Please enter [1] number:20
Please enter [2] number:45
Please enter [3] number:39
Please enter [4] number:25
Please enter [5] number:29
Please enter [6] number:7
Please enter [7] number:3
Please enter [8] number:2
Sorry they can't be constructed required cube!
*Thoughts
The method of establishing a full arrangement in a program is too inefficient. Although the algorithm is simple, the program is too redundant. Please design new algorithms to accomplish the same work by yourself.
63. Reduced restore
Write a program to solve the numbers represented by each letter in the following formula, and different letters represent different numbers.
PEAR
- ARA
——–
PEA
*Problem analysis and algorithm design
Similar problems are relatively simple from the perspective of computer algorithms and can be solved by the most common exhaustive method. The program uses a loop to exhaust the numbers that each letter may represent, and then convert the numbers represented by the letter into corresponding integers. After substituting them into the equation, verifying whether the equation is true to solve the problem.
*Program description and comments
#include<>
int main()
{
int p,e,a,r;
for(p=1;p<=9;p++) /*Exhaust all possible values of the letter p from 1 to 9*/
for(e=0;e<=9;e++) /*All possible values from 0 to exhaustive letter e*/
if(p!=e) /*p does not equal e*/
for(a=1;a<=9;a++) /*Exhaust all possible values of the letter a from 0 to 9*/
if(a!=p&&a!=e)
for(r=0;r<=9;r++) /*Exhaust all possible values of the letter r from 0 to 9*/
if(r!=p&&r!=e&&r!=a&&p*1000+e*100+a*10+r-(a*100+r*10+a)
==p*100+e*10+a)
{
printf(" PEAR %d%d%d%d\n",p,e,a,r);
printf(" -ARA - %d%d%d\n",a,r,a);
printf("…………………….\n");
printf(" PEA %d%d%d\n",p,e,a);
}
}
*Run result
PEAR 1098
- ARA - 989
———- ——
PEA 109
*Thoughts
Please restore the following formula. Different letters represent different numbers.
SEVEN 82524 82526
THREE 19722 19722
+ TWO Answer: + 106 + 104
———- ———– ———–
TWELVE 102352 102352
64. Multiplication restore
A represents the first five numbers in numbers 0 to 9, and Z represents the last five numbers. Please restore the following multiplication formula.
A Z A
× A A Z
————
A A A A
A A Z Z
Z A A
————
Z A Z A A
*Problem analysis and algorithm design
The problem itself is not complicated. You can use exhaustive method for each bit in the multiplication formula to finally get the result. The key to this question is how to effectively judge whether each bit of each part of each meets the question's meaning. If this problem is not handled well, the program written will be very long. A judgment function is used in the program implementation, and all numbers are uniformly judged by the flag string passed into the function.
*Program description and comments
#include<>
void print(long a,long b,long s1,long s2,long s3);
int jud(long q,char *pflag);
int main()
{
long i,j,k,l,m,n,term,t1,t2,t3;
int flag;
for(i=0;i<=4;++i) /*The first digit of the multiplier*/
for(j=5;j<=9;++j) /*The second digit of the multiplier*/
for(k=0;k<=4;++k) /*The third digit of the multiplier*/
{
term=100*i+10*j+k; /*Multiplied*/
for(flag=0,n=0;n<4&&!flag;) /*The first digit of the multiplier*/
flag=jud((t3=++n*100*term)/100,"001"); /*Judge the third part of the product*/
if(flag)
{
for(flag=0,m=0;m<4&&!flag;) /*The second digit of the multiplier*/
flag=jud((t2=++m*10*term)/10,"1100"); /*Judge the second part product*/
if(flag)
{
for(flag=0,l=5;l<9&&!flag;) /*The third digit of the multiplier*/
flag=jud(t1=++l*term,"0000"); /*Judge the first part of the product*/
if(flag&&jud(t1+t2+t3,"00101")) /*Judge product of multiplication*/
print(term,n*100+m*10+l,t1,t2,t3);
}
}
}
}
void print(long a, long b, long s1, long s2, long s3) /*Print result*/
{
printf("\n %ld\n",a);
printf("*) %ld\n",b);
printf("………………….\n");
printf(" %ld\n %ld\n %ld\n",s1,s2/10,s3/100);
printf("………………….\n");
printf(" %ld\n",a*b);
}
int jud(long q,char *pflag) /*The judgment function that determines whether each bit of a number meets the requirements*/
/*q: The number that needs to be judged. pflag: flag string, A is represented by 1, Z is represented by 0. The order of the logo string: ten hundred...*/
{
while(q!=0&&*pflag!=NULL) /*Cycle to determine whether the value range of the corresponding bit is correct*/
if(*pflag-'0'!=(q%10>=5?1:0)) /*Flat bit does not match the corresponding bit, return 0*/
return 0;
else
{
q/=10;++pflag; /*If it matches, take the next one for judgment*/
}
If(q==0&&*pflag==NULL) /*q's digit number is the same as the length of the flag string, return 1*/
return 1;
else return 0;
}
*Run result
3 7 2
× 2 4 6
———-
2 2 3 2
1 4 8 8
7 4 4
————
9 1 5 1 2
*Thoughts
E represents even numbers in numbers 0 to 9, and O represents odd numbers. Please restore the following multiplication formula.
E E O 2 8 5
× O O Answer × 3 9
———– ———–
E O E O 2 5 6 5
E O O 8 5 5
———– ———–
O O O O O 1 1 1 1 5
65. Multiplication Restore (2)
There are multiplication equations as follows:
○○○
× ○○
————
○○○○
○○○○
————
○○○○○
All 18 ○ positions are prime numbers (1, 3, 5 or 7). Please restore this formula.
*Problem analysis and algorithm design
Although there are 18 digits in the problem, the other digits can be determined as long as the multiplier and are multiplied and calculated.
There are 5 digits in total for multiplier and multiplied numbers, and each number is required to be a prime number. It is completely possible to use the exhaustive method to exhaust the multiplier and multiplier, and find the answer after judgment. However, this method gives people the feeling that it is "too stupid", because the numbers composed are only prime numbers (4), and there is no need to exhaust them within such a large range. It is just necessary to test the situation when each digit is a prime number.
The five-fold cycle method is used to achieve exhaustive results for 5 numbers, which have been seen in many previous examples. Loop implementation is simple and easy to use, but there are too many nested levels, and the number of exhaustive variables that directly affects the number of nested layers of the loop. This simple implementation method lacks skill. This example provides another algorithm with the same function. Please read the program for the implementation of this algorithm.
The program does not directly exhaust the prime numbers, but corresponds each prime number to the order of 1 to 4. When exhaustion, only exhaustive processing is performed for 1 to 4. When it is to be determined whether the generated product meets the conditions, an array is used to complete the conversion to the corresponding prime number. Please understand the processing methods in the program. The algorithm used in the program is actually the reciprocity method.
*Program description and comments
#include<>
#define NUM 5 /*Number of variables that need to be exhaustive*/
#define C_NUM 4 /*The range of changes in the value of each variable*/
int a[NUM+1]; /*Array for variables that need to be exhaustive*/
/*a[1]: the hundreds of digits multiplied, a[2]: ten digits, aa[3]: single digits a[4]: ten digits multiplied a[5]: single digits*/
int b[]={0,2,3,5,7}; /*Array of prime numbers, no element 0 is used*/
int f(long sum);
int main()
{
int i,not_finish=1;
i=2; /*i: The pointer subscript of the element to be processed. Set initial value*/
a[1]=1; /*Set the initial value for element 1*/
while(not_finish) /*not_finish: The program runs without ending mark*/
{
while(not_finish&&i<=NUM)
/* Process subsequent elements including the i-th element, and find a possible value method for each variable under the current conditions*/
if(a[i]>=C_NUM) /*When the element to be processed exceeds the specified C_NUM*/
if(i==1&&a[1]==C_NUM)
not_finish=0; /*If element 1 has reached C_NUM, all processing will end*/
else a[i–]=0; /* Set the element to be processed to 0, subscript -1 (return an element)*/
else a[i++]++; /*Add the current element value by adding 1 to the subscript pointer*/
if(not_finish)
{
long int sum1,sum2,sum3,sum4; /*Define temporary variable*/
sum1=b[a[1>*100+b[a[2>*10+b[a[3>; /*calculated multiplier*/
/*Use the corresponding relationship between the subscript of the array and the prime number to complete the conversion of the prime number from 1 to 4 to the prime number*/
sum2=sum1*b[a[5>; /* Calculate the partial product of the multiplier digits and the multiplier*/
sum3=sum1*b[a[4>; /* Calculate the partial product of the multiplier and the multiplier*/
if(sum2>=2222&&sum2<=7777&&f(sum2)&&sum3>=2222&&sum3<=7777&&f(sum3))
/*Judge whether the two-part product meets the question conditions*/
if((sum4=sum2+sum3*10)>=22222&&sum4<=77777&&f(sum4))
/*Judge whether the product of the multiplication meets the question conditions*/
{
printf(" %d\n",sum1); /*If the question is satisfied, print the result*/
printf("* %d%d\n",b[a[4>,b[a[5>);
printf("……………………\n");
printf(" %d\n",sum2);
printf(" %d\n",sum3);
printf("……………………\n");
printf(" %d\n",sum4);
}
i=NUM; /*Preparation for exhaustive next possible value*/
}
}
}
int f(long sum) /*Judge whether each digit of sum is a prime number. If it does not return 0, if it returns 1*/
{
int i,k,flag; /*flag=1: The number is a prime number mark*/
while(sum>0)
{
i=sum%10; /*Take the number of single digits*/
for(flag=0,k=1;!flag&&k<=C_NUM;k++)
if(b[k]==i)
{
flag=1;break;
}
if(!flag) return 0;
else sum=sum/10;
}
return 1;
}
*Run result
7 7 5
× 3 3
———-
2 3 2 5
2 3 2 5
———–
2 5 5 7 5
*Thoughts
In the following multiplication formula, A, B, and C represent a determined number, and ○ represents any number, please restore.
A B C 2 8 6
× B A C × 8 2 6
----- Answer: ----
○○○○ 1 7 1 6
○○A 5 7 2
○○○B 2 2 8 8
————- —————-
○○○○○○ 2 3 6 2 3 6
66. Deformation Restore (1)
Given the following division formula, which contains 5 7s, and the others that are × are any numbers, please restore them.
× 7 × ——————Business
————–
Divider—××|××××————— Divided
×7 7
————–
× 7 ×
× 7 ×
———-
× ×
× ×
———-
○
*Problem analysis and algorithm design
First, analyze the question and deduce as many known conditions as possible from the division itself. It is known from the book of division itself:
1. The range of the dividend is 10000 to 99999, and the range of the dividend is 10 to 99, and it can be divided in an integer manner;
2. The quotient is between 100 and 999, and the ten-digit number is 7;
3. The product of the first digit and the divisor of the quotient is a three-digit number, and the last two digits are 77;
4. The third bit of the dividend must be 4;
5. The product of 7 multiplied by the divisor is a three-digit number, and the second digit is 7;
6. The last digit of the quotient cannot be 0, and the product with the divisor is a two-digit number.
From known conditions, the results can be found using exhaustive methods.
*Program description and comments
#include<>
int main()
{
long int i;
int j,l;
for(i=10000;i<=99999;i++) /*1. i: Divided*/
if(i%1000-i%100==400) /*4. The third bit of the dividend must be 4*/
for(j=10;j<=99;j++) /*1. j: remainder*/
if(i%j==0&&(l=i/j)%100>=70&&l%100<80&&l%10!=0&&l>100&&l<=999)
/*1. Divided && 2. Quotation l is between 100 and 999 and ten digits are 7&&6. The number of quotients cannot be 0*/
if((j*(l%10))<100&&j*(l%10)>10) /*6. The product of the number of quotients and the divisor is a two-digit number*/
if(j*7%100>=70&&j*7%100<80) /*5. The second digit of the product of 7 times the divisor is 7*/
if(j*(l/100)%100==77&&j*(l/100)>100)
/*The last two digits of the product of the first quotient and the divisor are 77*/
printf("%ld/%ld=%d\n",i,j,l);
}
*Run result
51463/53=971。
It can be regarded as the following formula:
9 7 1
————-
5 3| 5 1 4 6 3
4 7 7
————-
3 7 6
3 7 1
———–
5 3
5 3
———–
○
* Further discussion of the problem
Among the known conditions for launch, several of the conditions are very obvious. In other words, the known conditions for launch are to describe the topic in a straightforward manner. This method of deducing known conditions is very simple and effective.
*Thoughts
Only one 8 is given in the following division formula. The other positions where × are marked are any number, please restore.
× 8 × ——————————————
—————-
Divider——-×××| ××××××———— Divided
××××
—————
×××
×××
—————
××××
××××
—————
○
67. Deformation Restore (2)
In the following division formula, only one 7 is given in the quotient. All other positions that hit × are arbitrary numbers, please restore.
×7××× ———————Business
——————
Divider ———————————××××| ×××××××××—————— Divided
×××× ————-1)
—————
××× ————-2)
××× ————-3)
—————
×××× ————-4)
××× ————-5)
—————–
×××× ————-6)
×××× ————-7)
—————–
0
*Problem analysis and algorithm design
This question cannot be solved by a simple exhaustive method. One is that the calculation time is too long, and the other is that it is difficult to find the values of each part of the division formula.
Analyze the division formula and introduce restrictions in multiple places:
From 3) we can see that the second digit of the quotient is multiplied by the divisor by a three-digit number, so the divisor is <=142.
By multiplying the first digit of the divisor to a four-digit number, it can be seen that the first digit of the quotient can only be 8 or 9 and the divisor >=112. At the same time, the fifth quotient is also the first four digits of 8 or 9 must be <=142*9+99 and >=1000+10.
From 4), 5), and 6) it can be seen that the first two digits of 4) must be "10"; the first two digits of 5) must be "9"; the first two digits of 6) must be between 10 and 99; the fourth digit of quotient must be 0.
From the first digit of 5) must be "9" and "112" <= divisor <= 142, we can see that the third digit of the quotient may be 7 or 8.
From the division formula itself, we can see that the fourth quotient is 0.
From 1) we can see that the first digit of the divisor X quotient should be a four-digit number.
From 5) we can see that the third digit of the divisor X quotient should be a three-digit number.
For the sake of convenience when programming, the dividend is decomposed: the first four digits are represented by a[0], the fifth digit is represented by a[1], the sixth digit is represented by a[2], the seventh and eighth digits are represented by a[3]; the divisor is represented by variable b; the decomposition quotient: the first digit is c[0], the fifth digit is represented by c[2]; the other partial quotients are represented by: the first two digits of 2) are d[0], the first three digits of 4) are d[1], and the first two digits of 6) are d[2]. The above analysis can be combined with mathematical methods as:
Divided number: 1010<=a[0]<=1377 0<=a[1]<=9
0<=a[2]<=9 0<=a[3]<=99
Divisor: 112<=b <=142
Quotation: 8<=c[0]<=9 7<=c[1]<=8 8<=c[2]<=9
The first two digits of 2): 10<=d[0]<=99
4) The top three digits: 100<=d[1]<b
The first two digits of 6): 10<=d[2]<=99
1) Partial product of formula: b*c[0]>1000
5) Partial product of formula: 100<b*c[1]<1000
*Program description and comments
#include<>
int main()
{
int a[4],b,c[3],d[4],i=1;
for(a[0]=1010;a[0]<=1377;a[0]++)
for(b=112;b<=142;b++)
for(c[0]=8;c[0]<=9;c[0]++)
if(b*c[0]>1000&&(d[0]=a[0]-b*c[0])>=10&&d[0]<100)
for(a[1]=0;a[1]<=9;a[1]++)
if((d[1]=d[0]*10+a[1]-b*7)>=100&&d[1]<b)
for(a[2]=0;a[2]<=9;a[2]++)
for(c[1]=7;c[1]<=8;c[1]++)
if(b*c[1]<1000&&(d[2]=d[1]*10+a[2]-b*c[1])>=10&&d[2]<100)
for(a[3]=0;a[3]<=99;a[3]++)
for(c[2]=8;c[2]<=9;c[2]++)
if(d[2]*100+a[3]-b*c[2]==0)
{
printf("No%2d:",i++);
printf("%d%d%d%d%d/",a[0],a[1],a[2],a[3]/10,a[3]%10);
printf("%d=",b);
printf("%d%d%d%d%d\n",c[0],7,c[1],0,c[2]);
}
}
*Run result:
No 1:12128316/124=97809
*Thoughts
In the following division formula, all the positions where "×" are located are arbitrary numbers, please restore.
×××××
——————-
××× | ××××××××
××××
——————
××××
×××
—————
×××
×××
———–
××××
××××
———–
0
68. Nine-digit progressive divisor
Find the nine-digit progressive divisor. The so-called nine-digit progressive divisor is such a number: this number consists of nine numbers 1 to 9, and each number only appears once. The first two digits of these nine digits can be divisible by 2, the first three digits can be divisible by 3... The first N digits can be divisible by N, and the entire nine digits can be divisible by 9.
*Problem analysis and algorithm design
The problem itself can be simplified into an exhaustive problem: as long as you exhaust the various possible values of each digit and judge the exhaustive results according to the requirements of the question, you will definitely get the correct result.
The problem gives the condition of "progressive derivation", which allows us to add conditional judgments to the exhaustive method. In the process of exhaustiveness, after determining the value of the partial bit, it is immediately determined whether the generated part meets the "progressive divisible" condition. If it meets, continue to exhaust the next digit; otherwise the digit just generated is wrong. In this way, the conditional judgment can be introduced into the exhaustive method, which can detect contradictions as early as possible and give up unnecessary exhaustive values as soon as possible, thereby improving the execution efficiency of the program.
In order to achieve the purpose of early detection of contradictions, multiple cycle methods cannot be used to implement exhaustive methods, as the quality of the programmed programs is poor. The algorithms used in the program are no longer exhaustive methods, but reciprocating methods.
*Program description and comments
#include<>
#define NUM 9
int a[NUM+1];
int main()
{
int i,k,flag,not_finish=1;
long sum;
i=1;
/*i: The array element being processed means that the first i-1 element has met the requirements, and the i-th element being processed*/
a[1]=1; /* Set initial value for element a[1]*/
while(not_finish) /*not_finish=1: Processing has not ended*/
{
while(not_finish&&i<=NUM)
{
for(flag=1,k=1;flag&&k<i;k++)
if(a[k]==a[i])flag=0; /*Judge whether the i-th element is repeated with the previous i-1 element*/
for(sum=0,k=1;flag&&k<=i;k++)
{
sum=10*sum+a[k];
if(sum%k)flag=0; /*Judge whether the integer composed of the first k bit can be divided by k*/
}
if(!flag) /*flag=0: means that the i-th position does not meet the requirements, and needs to be reset */
{
if(a[i]==a[i-1]) /*If the value of a[i] has been catching up with a[i-1]*/
{
i-; /* The value of i is reduced by 1, return to process the previous element*/
if(i>1&&a[i]==NUM)
a[i]=1; /*When the value of the i-th position reaches NUM, the value of the i-th position is 1*/
else if(i==1&&a[i]==NUM) /*End when the value of the first bit reaches NUM*/
not_finish=0; /*Set the program end flag*/
else a[i]++; /*The value of the i-th position is taken next, add 1*/
}
else if(a[i]==NUM) a[i]=1;
else a[i]++;
}
else /*The i-th position has met the requirements, and the i-th position is handled*/
if(++i<=NUM) /*i+1 handles the next element, when i is not processed*/
if(a[i-1]==NUM) a[i]=1; /*If the value of i-1 is already NUM, then the value of a[i] is 1*/
else a[i]=a[i-1]+1; /* Otherwise, the initial value of a[i] is the "next" value of a[i-1]*/
}
if(not_finish)
{
printf("\nThe progressire divisiable number is:");
for(k=1;k<=NUM;k++) /*Output calculation result*/
printf("%d",a[k]);
if(a[NUM-1]<NUM) a[NUM-1]++;
else a[NUM-1]=1;
not_finish=0;
printf("\n");
}
}
}
*Run result
The progressire divisible number is: 381654729
*Thoughts
Find the N-bit progressive divisor. Use nine numbers from 1 to 9 to form an N(3<=N<=9) digit number. The composition of the digit number is unlimited, so that the first two digits of the N digit number can be divisible by 2, the first 3 digits can be divisible by 3,..., the first N digit can be divisible by N. Find the N-digit number that satisfies the condition.
69. Magician's card guessing technique (1)
The Magician uses 13 spades in a deck of cards to arrange them in advance and stack them together, with the cards facing down. Say to the audience: I don’t look at cards, I can guess what each card is by just counting. I count loudly. Do you listen, don’t you believe it? You just see. The magician put the number of the top card to 1, flipped it over and was exactly A spade A, put spade A on the table, and then count the remaining cards on the hand from top to bottom in order, with the second number of 1 and 2, put the first card under the card, flipped the second card, which happened to be 2 spades, and also put it on the table, with the third number of 1, 2 and 3, put the first two cards under the card, and then flipped the third card to be exactly 3 spades. This way, all 13 cards are turned out in sequence, and it is accurate. Ask the magician how the original order of cards in his hand was arranged?
*Problem analysis and algorithm design
The question has clearly described the magician’s card-playing process, and we can easily deduce the original card sequence using the reverse push method.
The method of manual backward push is: put 13 empty boxes on the table in a circle, number them in sequence starting from 1, put spades A into box No. 1, count the empty boxes from the next empty box, and when counting the second empty box, put spades 2 into the empty box, and then count the empty boxes from the next empty box, and put 3, 4, 5... in sequence until all 3 cards are placed. Note that non-empty boxes should be skipped when counting and count only empty boxes. The order of the last cards in the box is the order of the original cards in the magician's hand.
This manual method is effective and computers can simulate and solve.
*Program description and comments
#include<>
int a[14];
int main()
{
int i,n,j=1; /*j: Array (box) subscript, initially it is element 1*/
printf("The original order of cards is:");
for(i=1;i<=13;i++) /*i: The serial number of the card to be placed in the box*/
{
n=1;
do{
if(j>13) j=1; /*Because the box forms a circle, j exceeds the last element and points to element 1*/
if(a[j]) j++; /*Skip non-empty boxes and do not count*/
else{ if(n==i) a[j]=i; /*If the i-th empty box is counted, put the card into the empty box*/
j++;n++; /*Count the empty box, the array subscript points to the next box*/
}
}while(n<=i); /*Control empty box count is i*/
}
for(i=1;i<=13;i++) /*Order order of output cards*/
printf("%d ",a[i]);
printf("\n");
}
*Run result
The original order of cards is:1 8 2 5 10 3 12 11 9 4 7 6 13
70. Magician's card guessing technique (2)
The magician performed again. He stacked the hearts and spades together, put the cards face down in his hand, and said to the audience: The top one is A spades, and then put them on the table after turning them open. After that, every two pictures from top to bottom is placed at the bottom, and the third one is for the audience to show, which is Spade 2. After putting it on the table, it counts two pictures and puts them at the bottom, and the third one is for the audience to show, which is Spade 3. If this continues, the order in which the audience sees the cards placed on the table is:
Spades A 2 3 4 5 6 7 8 9 10 J Q K
Heart A 2 3 4 5 6 7 8 9 10 J Q K
Ask the magician what the original order of the cards in his hand?
*Problem analysis and algorithm design
This question can be programmed based on the previous question. The difference lies in the counting method and the number of cards. These do not affect our thinking of solving the problem. You can still obtain the order of cards in the magician's hands according to the reverse deduction method.
*Program description and comments
#include<>
int a[27];
int main()
{
int i,n,j=1;
a[1]=1; /*Initialize the first card*/
printf("The original order of cards is:(r:rad b:block):\n");
for(i=2;i<=26;i++)
{
n=1;
do{
if(j>26) j=1; /*If the last element exceeds the point to element 1*/
if(a[j]) j++; /*Skip non-empty boxes and do not count*/
else{
if(n==3) a[j]=i; /*If you count to the third empty box, put the card into the empty box*/
j++; n++; /*Count the empty box, the array subscript points to the next box*/
}
}while(n<=3); /*Control empty box count is 3*/
}
for(i=1;i<=26;i++) /*Order order of output cards*/
{
printf("%c",a[i]>13? 'r':'b');
printf("%d ",a[i]>13? a[i]-13:a[i]);
if(i==13) printf("\n");
}
printf("\n");
}
*Run result
The original order of cards is:(r:rad b:black):
b1 r6 b10 b2 r12 r3 b3 b11 r9 b4 r7 b12 b5
r4 r13 b6 b13 r11 b7 r5 r1 b8 r8 r10 b9 r2
Hundreds of exquisite explanations for classic, practical and interesting programming of C/C++ language (8)
71. Joseph's Problem
This is a story told by the 17th-century French mathematician Gasper in "The Problem of Numbers": 15 believers and 15 non-confucians were in danger in the deep sea. Half of the people had to be thrown into the sea, so the rest could survive. So they thought of a solution: 30 people formed a circle, and counted in turn from the first person to the ninth person. Every time they counted to the ninth person, they threw him into the sea, and the cycle continued until only 15 people remained. Ask how to arrange the method so that every time you throw yourself into the sea, you are non-confucians.
*Problem analysis and algorithm design
The Joseph problem is not difficult, but there are many solutions; there are many variations in the question. Here is a method of implementation.
The 30 people in the question are in a circle, which inspires us to express it with a circular chain. A structure array can be used to form a circular chain. There are two members in the structure, one is a pointer to the next person to form a ring-shaped chain; the other is a mark of whether the person was thrown into the sea, and one means that he is still on the ship. Starting from the first person, counting people who have not been thrown into the sea, every time they count to 9, the mark in the structure is changed to 0, indicating that the person has been thrown into the sea. This cycle counts until 15 people are thrown into the sea.
*Program description and comments
#include<>
struct node
{
int nextp; /* Pointer to the next person (the next person's array subscript)*/
int no_out; /*The mark of whether it is thrown into the sea. 1: Not thrown into the sea. 0: Has been thrown into the sea*/
}link[31]; /*30 people, element 0 is not used*/
int main()
{
int i,j,k;
printf("The original circle is(+:pagendom,@:christian):\n");
for(i=1;i<=30;i++) /*Initialize the structure array*/
{
link[i].nextp=i+1; /*Pointer point to the next person (array element subscript)*/
link[i].no_out=1; /* flag set to 1, indicating that everyone is on the ship*/
}
link[30].nextp=1; /*The pointer of the 30th person points to the first person to form a ring*/
j=30; /*j: Point to the processed array element, counting from the person pointed to by link[i]*/
for(i=0;i<15;i++) /*i: The number of people who have been thrown into the sea*/
{
for(k=0;;) /*k: The counter that determines who is thrown into the sea*/
if(k<15)
{
j=link[j].nextp; /*Modify the pointer and take down a person*/
k+=link[j].no_out; /* for counting. Because the person who has been thrown into the sea is marked as 0*/
}
else break; /* Count to 15 and stop counting*/
link[j].no_out=0; /* Set the mark 0 to indicate that the person has been thrown into the sea*/
}
for(i=1;i<=30;i++) /*Output result*/
printf("%c",link[i].no_out? '@':'+'); /*+: Throwed down from the sea, @: on the ship*/
printf("\n");
}
*Run result
The original circle is(+:pagandom, @:christian):
+++@@+@+@@@+@+++@@+@@@+++@+@@+
(+" means non-congregation who was thrown into the sea @: the congregation who stayed on the boat)
*Thoughts
There are N children in a circle and number them in turn. The teacher specifies that the number will start from the M-th child, and the child will be removed from the list when the S-th child is reported. Then continue to count from the next child, count to the S-th child and let him be removed, so that all the children are removed. Ask the order of children's delisting.
72. Stamp combination
How many different postage can someone get if he has four 3-cent stamps and three 5-cent stamps?
*Problem analysis and algorithm design
The problem is mathematically analyzed, and the postage composed of stamps of different numbers and face values can be calculated using the following formula:
S=3*i+5*j
where i is the number of stamps with 3 points and j is the number of stamps with 5 points
According to the requirements of the question, 3-point stamps can be 0, 1, 2, 3, and 4 stamps, and 5-point stamps can be 0, 1, 2, and 3. By combining the exhaustive method, the postage price after the combination of these postage tags with different face value and different numbers can be obtained.
*Program description and comments
#include<>
int a[27];
int main()
{
int i,j,k,s,n=0;
for(i=0;i<=4;i++) /*i: Take the number of three-point stamps*/
for(j=0;j<=3;j++) /*j: Take the number of stamps with 5 points*/
{
s=i*3+j*5; /*The calculated face value of the stamp*/
for(k=0;a[k];k++) /*Search for if there is the same postage*/
if(s==a[k])break;
if(!a[k]&&s) /*If the same postage is not found, it will be deposited into the array as required*/
{
a[k]=s; n++;
}
}
printf("%d kinds:",n); /*Output result*/
for(k=0;a[k];k++)
printf("%d ",a[k]);
printf("\n");
}
*Run result
19 kinds: 5 10 15 3 8 13 18 6 11 16 21 9 14 19 24 12 17 22 27
73. The sum can represent 5 positive integers from 1 to 23.
It is known that the sum of five positive integers that are different from each other is 23, and selecting several of the five numbers to represent all natural numbers from 1 to 23. What are these five numbers?
*Problem analysis and algorithm design
From the perspective of computer programming, 23 can be decomposed using the exhaustive method, and then judge whether the five decomposed numbers can represent all integers between 1 and 23.
*Program description and comments
#include<>
int main()
{
int a,b,c,d,e,i,j,k,l,m,x,count=0,f=0; /*f: The decomposed 5 numbers can represent the marks of 1~23*/
printf("There are following possble result:\n");
for(a=1;a<=23;a++) /*Decompose 23 into five numbers: a,b,c,d,e*/
for(b=1+a;b<=23-a;b++)
for(c=1+b;c<=23-a-b;c++)
for(d=1+c;d<=23-a-b-c;d++)
{
f=1;
if((e=23-a-b-c-d)>d)
for(f=0,x=1;x<24&&!f;x++) /*Judge whether 5 numbers can represent 1~23*/
for(f=1,i=0;i<2&&f;i++) /* Exhaust all choices of 5 numbers*/
for(j=0;j<2&&f;j++)
for(k=0;k<2&&f;k++)
for(l=0;l<2&&f;l++)
for(m=0;m<2&&f;m++)
if(x==a*i+b*j+c*k+d*l+e*m) f=0;
if(!f) printf("[%d]: %d %d %d %d %d\n",++count,a,b,c,d,e);
}
}
*Run result
There are following possble result:
[1]: 1 2 3 5 12
[2]: 1 2 3 6 11
[3]: 1 2 3 7 10
[4]: 1 2 4 5 11
[5]: 1 2 4 6 10
[6]: 1 2 4 7 9
74. 4 weights that can weigh 1 to 40 pounds
French mathematician Meziac asked a question in his famous "The Game of Numbers" (1962): a businessman had a weight weighing 40 pounds and accidentally threw the weight into four pieces a day. Later, the merchant claimed that the weight of each piece was a whole pound, and found that these four pieces could be weighed on the balance of any weight between 1 and 40 pounds. How much does these four pieces weigh?
*Problem analysis and algorithm design
This question is the development of the previous question. The condition given in the question is "on the balance", which means that the same weight can be placed on either the left side of the balance or on the right side of the balance. If it is stipulated that heavy objects can only be placed on the left side of the balance, when the balance is balanced, there are:
Weight of weight + sum of weight on the left side = sum of weight on the right side
From this we can obtain:
Weight = sum of weights on the right-weights - sum of weights on the left
When programming, just follow the above formula to make the "right weight sum - left weight sum" represent the entire weight between 1 and 40. What you need to pay attention to in programming is how to use a simple method to indicate whether a weight is on the left side of the balance or on the right side of the balance, or is not used at all.
The following program uses 1, -1 and 0 to represent the above three situations, please be careful to understand.
*Program description and comments
#include<>
#include<>
int main()
{
int weight1,weight2,weight3,weight4,d1,d2,d3,d4,x,flag; /*flag: mark that satisfies the question*/
printf("The weight is broke up as following 4 pieces:");
for(weight1=1;weight1<=40;weight1++) /*Decompose 40 into 4 parts*/
for(weight2=weight1+1;weight2<=40-weight1;weight2++)
for(weight3=weight2+1;weight3<=40-weight1-weight2;weight3++)
if((weight4=40-weight1-weight2-weight3)>=weight3)
{
for(flag=1,x=1;x<41&&flag;x++) /*Judge whether you can weigh the entire weight between 1 and 40*/
for(flag=0,d1=1;d1>-2;d1–) /*Put the heavy object to the left of the balance*/
for(d2=1;d2>-2&&!flag;d2–) /*1: The weight is on the right side of the balance*/
for(d3=1;d3>-2&&!flag;d3–) /*0: Do not use this weight*/
for(d4=1;d4>-2&&!flag;d4–) /*-1: The weight is on the left side of the balance*/
if(x==weight1*d1+weight2*d2+weight3*d3+weight4*d4)
flag=1;
if(flag) printf("%d %d %d %d\n",weight1,weight2,weight3,weight4);
flag=0;
}
}
*Run result
The weight is broke up as following 4 pieces: 1 3 9 27
75.10 Children share candy
Ten children gathered in a circle to divide candy. The teacher gave the first child 10 yuan, the second child 2 yuan, the third child 8 yuan, the fourth child 22 yuan, the fifth child 16 yuan, the sixth child 4 yuan, the seventh child 10 yuan, the eighth child 6 yuan, the ninth child 14 yuan, and the tenth child 20 yuan. Then all the children will give half of the sugar in their hands to the child on the right at the same time; those with odd numbers of candy can ask the teacher for a piece. After several times, do you have the same amount of sugar in your hands? How many pieces of candy do each person have?
*Problem analysis and algorithm design
The sugar-sharing process described in the question is a mechanical repetitive process, and the programming algorithm can be simulated completely according to the described process.
*Program description and comments
#include<>
void print(int s[]);
int judge(int c[]);
int j=0;
int main()
{
static int sweet[10]={10,2,8,22,16,4,10,6,14,20}; /*Initialize array data*/
int i,t[10],l;
printf(" child\n");
printf(" round 1 2 3 4 5 6 7 8 9 10\n");
printf("………………………..\n");
print(sweet); /*Output the number of sugar in each person's hand*/
while(judge(sweet)) /*If the requirements are not met, continue the loop*/
{
for(i=0;i<10;i++) /*Divide the sugar in each person's hand into half*/
if(sweet[i]%2==0) /*If it is an even number, it will be divided directly by half*/
t[i]=sweet[i]=sweet[i]/2;
else /*If it is an odd number, add 1 and then divide half*/
t[i]=sweet[i]=(sweet[i]+1)/2;
for(l=0;l<9;l++) /*Give half of the sugar you have distributed to the child on the right (back)*/
sweet[l+1]=sweet[l+1]+t[l];
sweet[0]+=t[9];
print(sweet); /*Output the current number of sugars in each child*/
}
}
int judge(int c[])
{
int i;
for(i=0;i<10;i++) /*Judge whether the sugar in each child's hands is the same*/
if(c[0]!=c[i]) return 1; /*Not the same return 1*/
return 0;
}
void print(int s[]) /*Output the value of each element in the array*/
{
int k;
printf(" %2d ",j++);
for(k=0;k<10;k++) printf("%4d",s[k]);
printf("\n");
}
76. Xiao Ming buys books
Xiao Ming went to the bookstore with his father during the holidays. He selected six books, and the unit prices of each book were: 3.1, 1.7, 2, 5.3, 0.9 and 7.2 respectively. Unfortunately, Xiao Ming's father only brought more than ten yuan. In order to let Xiao Ming have a happy holiday, his father agreed to buy a book, but he asked Xiao Ming to select several books from the six books, so that the combined unit price is closest to the same as 10. Can you help Xiao Ming solve this problem?
*Problem analysis and algorithm design
By analyzing the meaning of the question, you can simplify the question to: select several sums from six numbers, so that the difference between sum and 10 is minimized.
There are two problems hidden in the question: one is how to select several numbers from six numbers; the other is to find the difference between 10.
Selecting several numbers from six numbers is essentially selecting several numbers from six numbers for combination. There are only two situations in the combination process of each number: either select to participate in the sum, or do not select to participate in the sum. This allows you to use a six-fold cycle to combine all possible cases whether each number participates in the sum.
Regarding finding the difference between 10, it should be noted that the difference means the absolute value of the difference. For example: "9-10=-1" and "11-10=1", but the difference between 9 and 11 and 10 is 1. It would be wrong to think that the difference between "9" and "10 is -1.
*Program description and comments
#include<>
#include<>
int main()
{
int d[6],m,i,j;
long b[63],flag;
float c[6],min,x;
printf("Please enter the prices of 6 books:");
for(i=0;i<6;i++) scanf("%f",&c[i]); /*Input six floating point numbers*/
for(i=0,min=-1,d[0]=0;d[0]<2;d[0]++) /*Create all combinations of six numbers and process*/
for(d[1]=0;d[1]<2;d[1]++) /*i: The difference has the number of min combinations*/
for(d[2]=0;d[2]<2;d[2]++) /*min: The minimum difference between 10*/
for(d[3]=0;d[3]<2;d[3]++) /*d[]: Whether to take the flag of this number when combining*/
for(d[4]=0;d[4]<2;d[4]++)
for(d[5]=0;d[5]<2;d[5]++)
{
for(flag=0,x=0,j=5;j>=0;j–)
/*flag: Use the corresponding decimal bit to represent the sum of the six numbers*/
{
x+=c[j]*d[j]; flag=flag*10+d[j];
}
x=((x-10>0)? x-10:10-x); /*x: The difference between the combined sum and 10*/
if(min<0)
{
min=x; /*process the first calculated difference min*/
b[i++]=flag; /*b[]: Array with the same min flag i: the subscript of the array of b[]*/
}
else if(min-x>-6) /*Treatment of new min*/
{
min=x; b[0]=flag; i=1;
}
else if(fabs((double)x-min)<-6)
b[i++]=flag; /*Treatment of equal min*/
}
for(m=0;m<i;m++) /*Outputs the combination of all the differences between i and 10 and min*/
{
printf("10(+ -)%.2f=",min);
for(flag=b[m],j=0;flag>0;j++,flag/=10)
if(flag%10) /*Restore the flag stored in b[] to a combination of each number*/
if(flag>1) printf("%.2f+",c[j]);
else printf("%.2f\n",c[j]);
}
}
*Run result
Please enter the prices of 6 books:3.1 1.7 2.0 5.3 0.9 7.2
10(+ -)0.10=2.00+0.90+7.20
10(+ -)0.10=1.70+2.00+5.30+0.90
10(+ -)0.10=3.10+1.70+5.30
*Thoughts
It can be seen that the algorithm that can produce all combinations of six numbers in the program is not good, and using six-fold loops to process the program seems not concise enough. More general and optimized algorithms can be designed to produce all combinations.
77. Interesting questions about Posunwa wine sharing
The famous French mathematician Povason studied an interesting mathematical problem in his lunar calendar: someone has 12 pints of beer and wants to pour 6 pints out of it, but he does not have a container of 6 pints, only an 8 pint and a 5 pints of container. How can he pour the beer into two 6 pints?
*Problem analysis and algorithm design
Divide the empty bottles of 12 pints of wine, 8 pints and 5 pints in a bisect, and you can abstract it into solving indefinite equations:
8x-5y=6
The meaning is: pour x times from a 12 pint bottle into an 8 pint bottle, and pour the wine from a 5 pint bottle into an 12 pint bottle, and finally the wine remaining in the 12 pint bottle.
Use a, b, and c to represent bottles of 12 pints, 8 pints and 5 pints to find the integer solution of the indefinite equation. According to the meaning of the indefinite equation, the reverse method is:
a -> b -> c ->a
x y
The rules for pouring wine are as follows:
1) In the order of a -> b -> c -> a;
2) Only after b is empty can it be taken from a
3) C can only pour into a
According to the above rules, the program can be written as follows:
*Program description and comments
#include<>
void getti(int a,int y,int z);
int i; /*The weight required to be distributed in the end*/
int main()
{
int a,y,z;
printf("input Full a,Empty b,c,Get i:"); /*a The capacity of the full bottle y: the capacity of the first empty bottle z: the capacity of the second empty bottle*/
scanf("%d%d%d%d",&a,&y,&z,&i);
getti(a,y,z); /*Press a -> y -> z -> a operation steps*/
getti(a,z,y); /*Press a -> z -> y -> a step*/
}
void getti(int a,int y,int z) /*a: The capacity of the full bottle y: The capacity of the first empty bottle z: The capacity of the second empty bottle*/
{
int b=0,c=0; /* b: The actual weight of the first bottle c: The actual weight of the second bottle*/
printf(" a%d b%d c%d\n %4d%4d%4d\n",a,y,z,a,b,c);
while(a!=i||b!=i&&c!=i) /*When the full bottle!=i or the other two bottles are!=i*/
{
if(!b)
{ a-=y; b=y;} /*If the first bottle is empty, pour the full bottle into the first bottle*/
else if(c==z)
{ a+=z; c=0;} /*If the second bottle is full, pour the second bottle into the full bottle*/
else if(b>z-c) /*If the weight of the first bottle > the remaining space of the second bottle*/
{ b-=(z-c);c=z;} /*The second bottle will be filled, and the remaining part will be retained in the first bottle*/
else{ c+=b; b=0;} /* Otherwise, pour all the first bottle into the second bottle*/
printf(" %4d %4d %4d\n",a,b,c);
}
}
*Thoughts
The above program only gives two methods of distributing wine, but no all methods are found. Please design a new algorithm to find all the methods of dividing wine, and find a method with the least amount of wine poured.
78. Find the approximate value of π
Please use the "regular polygon approximation" method to find the approximation of π
*Problem analysis and algorithm design
Using the method of "regular polygon approximation" to find that the π value existed a long time ago. Our ancestors and ancestors used this method to obtain the π value with an accuracy of 6th place after the decimal point in the world.
Use the characteristic that the edge length of a regular hexagon in the circle is equal to the radius to double the edge number, make a regular dodecagon, calculate the edge length, and repeat this process to obtain an approximation of π of the required accuracy.
Assuming that the edge length of the polygon in the unit circle is 2b and the edge number is i, then the edge length of the new regular polygon after the edge number is doubled is:
x=√──────
2-2*√───
1-b*b
──────
2
The circumference is:
y=2 * i * x i: is the number of sides of the regular polygon before doubling
*Program description and comments
#include<>
#include<>
int main()
{
double e=0.1,b=0.5,c,d;
long int i; /*i: number of regular polygon sides*/
for(i=6;;i*=2) /*Double the edge number of regular polygons*/
{
d=1.0-sqrt(1.0-b*b); /* Calculate the side length of the regular polygon in the circle*/
b=0.5*sqrt(b*b+d*d);
if(2*i*b-i*e<1e-15) break; /*The calculation will be stopped if the accuracy reaches 1e-15*/
e=b; /*Save the side length of this regular polygon as the basis for the next precision control*/
}
printf("pai=%.15lf\n",2*i*b); /*Output π value and number of sides of regular polygon*/
printf("The number of edges of required polygon:%ld\n",i);
}
*Run result
pai=3.141592653589794
The number of edges of required polygon:100663296
*Thoughts
Please use the method of tangent regular polygon approximation to find the approximation of π.
79. Find the approximate value of π (2)
Use random number method to find the approximate value of π
*Problem analysis and algorithm design
The idea of finding the approximate value of π by random number method: in a square with unit side length, the side length is the radius and a vertex as the center, and a quarter circle is made on the square of the regime. Randomly throw points into the square, and count if they fall into a quarter circle. Repeat throwing enough points into the square to divide the count falling into a quarter circle by the total number of points, and its value is an approximation of a quarter of the value of π.
You can directly program according to this method. Note: The π value obtained in this method can only be accurate if there are enough statistics.
*Program description and comments
#include<>
#include<>
#include<>
#define N 30000
int main()
{
float x,y;
int c=0,d=0;
randomize();
while(c++<=N)
{
x=random(101); /*x:Coordinates. Generate a total of 101 random numbers between 0 and 100*/
y=random(101); /*y: coordinates. Generate a total of 101 random numbers between 0 and 100*/
if(x*x+y*y<=10000) /*Use the circle equation to determine whether the point falls within the circle*/
d++;
}
printf(" pi=%f\n",4. *d/N); /*Output the calculated π value*/
}
*Run result
Running the program multiple times can result in multiple different counterparts. This is because the approximate values obtained by statistical rules are used. Only when the number of statistics is large enough can the π value be approached. Run four times, the possible results are:
3.122267
3.139733
3.133733
80. An interesting property of odd squares
Programming verification "Odd numbers greater than 1000 have a difference of square and 1 are multiples of 8".
*Problem analysis and algorithm design
This question is an easy-to-prove mathematical theorem, we can write programs to verify it.
The processing process given in the question is very clear, and the algorithm does not require special design. Verification can be performed directly according to the description of the question (only 3000 is verified in the program).
*Program description and comments
#include<>
int main()
{
long int a;
for(a=1001;a<=3000;a+=2)
{
printf("%ld:",a); /*Output odd numbers themselves*/
printf("(%ld*%ld-1)/8",a,a); /*Output (Odd square minus 1)/8*/
printf("=%ld",(a*a-1)/8); /*The output quotient after being divided by 8*/
printf("+%ld\n",(a*a-1)%8); /*Output remainder after being divided by 8*/
}
}
Hundreds of exquisite explanations for classic, practical and interesting programming of C/C++ language (9)
81. Kakuya Guest
A Japanese middle school student discovered a wonderful "theorem" and asked Professor Kakutani to prove it, but the professor was powerless, so he developed Kakutani's conjecture. The conjecture is: give a natural number, if it is an even number divided by 2, if it is an odd number, multiply 3 and add 1, obtain a new natural number and continue to calculate according to the above rules. The result obtained after several times must be 1. Please program verification.
*Problem analysis and algorithm design
This question is a conjecture that has not been obtained in general proof, but it has been tried and proved by the program.
The processing process given in the question is very clear. The algorithm does not require special design and can be directly verified according to the description of the question.
*Program description and comments
#include<>
int main()
{
int n,count=0;
printf("Please enter number:");
scanf("%d",&n); /*Enter any integer*/
do{
if(n%2)
{
n=n*3+1; /*If it is an odd number, n times 3 plus 1*/
printf("[%d]:%d*3+1=%d\n",++count,(n-1)/3,n);
}
else
{
n/=2; /*If it is an even number n divided by 2*/
printf("[%d]: %d/2=%d\n",++count,2*n,n);
}
}while(n!=1); /*n does not equal 1, then continue the above process*/
}
82. Four-way theorem
The famous "Four-Square Theorem" in number theory says that all natural numbers can be expressed as at most by the sum of squares of four numbers.
Please program and verify this theorem.
*Problem analysis and algorithm design
This question is a theorem, we do not prove it but program verification.
The four variables are calculated using a tentative method, and the calculation results are output when they meet the requirements.
*Program description and comments
#include<>
#include<>
int main()
{
int number,i,j,k,l;
printf("Please enter a number=");
scanf("%d",&number); /*Input integer*/
for(i=1;i<number/2;i++) /*Test method. Test the different values of i,j,k,k*/
for(j=0;j<=i;j++)
for(k=0;k<=j;k++)
for(l=0;l<=k;l++)
if(number==i*i+j*j+k*k+l*l) /*If the theorem requirements are met, the result will be output*/
{
printf(" %d=%d*%d+%d*%d+%d*%d+%d*%d\n",number,i,i,j,j,k,k,l,l);
exit(0);
}
}
*Run result
1) Please enter a number = 110
110=7*7+6*6+4*4+3*3
2) Please enter a number = 211
211=8*8+7*7+7*7+7*7
3) Please enter a number = 99
99=7*7+5*5+4*4+3*3
83.Capric constant
Verify the Cabrec operation. For any four-digit number, as long as the numbers on each digit are not the same, there is a rule:
1) Arrange the four numbers that make up the four digits from large to small to form the largest four digit number composed of these four digits;
2) Arrange the four numbers that make up the four digits from small to large to form the smallest four digit number composed of these four digits (if the four numbers contain 0, the resulting number is less than four digits);
3) Find the difference between two numbers and get a new four-digit number (high zero reserved).
Repeat the above process and the final result is 6174, which is called the Cabrec number.
*Problem analysis and algorithm design
The processing process given in the question is very clear. The algorithm does not require special design and can be directly verified according to the description of the question.
*Program description and comments
#include<>
void vr6174(int);
void parse_sort(int num,int *each);
void max_min(int *each,int *max,int *min);
void parse_sort(int num,int *each);
int count=0;
int main()
{
int n;
printf("Enter a number:");
scanf("%d", &n); /*Input any positive integer*/
vr6174(n); /*Calling the function for verification*/
}
void vr6174(int num)
{
int each[4],max,min;
if(num!=6174&&num) /*If it is not equal to 74 and not equal to 0, then perform the Cabrec operation*/
{
parse_sort(num,each); /*Decompose integers and save numbers into each array*/
max_min(each,&max,&min); /*Find the maximum and minimum values of numbers*/
num=max-min; /* Find the difference between the maximum value and the minimum value*/
printf("[%d]: %d-%d=%d\n",++count,max,min,num); /*Output this step of calculation process*/
vr6174(num); /*Recursive call itself continues to perform Cabrec operation*/
}
}
void parse_sort(int num,int *each)
{
int i,*j,*k,temp;
for(i=0;i<=4;i++) /*Decompose NUM into numbers*/
{
j=each+3-i;
*j=num%10;
num/=10;
}
for(i=0;i<3;i++) /*Sort each guarantee number from small to large*/
for(j=each,k=each+1;j<each+3-i;j++,k++)
if(*j>*k) { temp=*j;*j=*k;*k=temp;}
return;
}
void max_min(int *each,int *max,int *min) /*Restore the decomposed number to the maximum integer and the minimum integer*/
{
int *i;
*min=0;
for(i=each;i<each+4;i++) /*Restore to the smallest integer*/
*min=*min*10+*i;
*max=0;
for(i=each+3;i>=each;i-) /*Restore to the largest integer*/
*max=*max*10+*i;
return;
}
*Run result
1) Enter a number:4312
[1]:4312-1234=3078
[2]:8730-378=8352
[3]:8532-2358=6174
2) Enter a number:8720
[1]:8720-278=8442
[2]:8442-2448=5994
[3]:9954-4599=5355
[4]:5553-3555=1998
[5]:9981-1899=8082
[6]:8820-288=8523
[7]:8532-2358=6174
3)Enter a number:9643
[1]:9643-3469=6174
84. Nicoches Theorem
Verify Nicoches' theorem, that is, any cube of an integer can be written as a series of consecutive odd numbers. ××
*Problem analysis and algorithm design
This question is a theorem, let’s first prove that it is valid.
For any positive integer a, whether a is an odd or even number, the integer (a×a-a+1) must be an odd number.
Construct an arithmetic sequence. The first term of the sequence is (a×a-a+1), and the difference of the arithmetic sequence is 2 (odd sequence), then the sum of the previous term a is:
a×((a×a-a+1))+2×a(a-1)/2
=a×a×a-a×a+a+a×a-a
=a×a×a
The theorem holds. Completed the certification.
Through the proof process of the theorem, it can be seen that the first term of the odd number sequence required by L is (a×a-a+1) and the length is a. Programmed algorithms do not require special designs, and can be verified directly according to the proof of the theorem.
*Program description and comments
#include<>
int main()
{
int a,b,c,d;
printf("Please enter a number:");
scanf("%d",&a); /*Input integer*/
b=a*a*a; /*Find the cubic power of an integer*/
printf("%d*%d*%d=%d=",a,a,a,b);
for(d=0,c=0;c<a;c++) /*Output sequence, the first term is a*a-a+1, the arithmetic value is 2*/
{
d+=a*a-a+1+c*2; /*Find the sum of the previous term a of the sequence*/
printf(c?"+%d":"%d",a*a-a+1+c*2);
}
if(d==b)printf(" Y\n"); /*If the condition is satisfied, output "Y"*/
else printf(" N\n"); /* Otherwise output "N"*/
}
*Run result
1) Please enter a number:13
13*13*13=2197=157+159+161+163+165+167+169+171+173+175+177+179+181 Y
2) Please enter a number:14
14*14*14=2744=183+185+187+189+191+193+195+197+199+201+203+205+207+209 Y
*Thoughts
The solution to this problem is to first prove, find the programming algorithm in the process of proof, and then implement programming. In fact, we can also use the commonly used test methods in programming to find the sequence and verify the theorem without proofing. Please design the algorithm yourself. Of course, the sequence obtained in this way may be different from the sequence obtained by the theorem method.
85. The formation of palindrome numbers
Take any decimal integer, add it to the original integer, get a new integer, and repeat the above steps to finally get a palindrome number. Please program verification.
*Problem analysis and algorithm design
This rule of forming palindrome numbers is still a conjecture and has not been proved mathematically. Some palindromes take hundreds of steps to obtain. This is programmed verified here.
The processing process given in the question is very clear, and the algorithm does not require special design. It can be directly verified according to the description of the question.
*Program description and comments
#include<>
#define MAX 2147483647
long re(long int);
int nonres(long int s);
int main()
{
long int n,m;
int count=0;
printf("Please enetr a number optionaly:");
scanf("%ld",&n);
printf("The generation process of palindrome:\n");
while(!nonres((m=re(n))+n)) /*Judge whether an integer and its inverse number are palindrome numbers after adding them*/
{
if(m+n>=MAX)
{
printf(" input error,break.\n");
break;
}
else
{
printf("[%d]:%ld+%ld=%ld\n",++count,n,m,m+n);
n+=m;
}
}
printf("[%d]:%ld+%ld=%ld\n",++count,n,m,m+n); /*Output the last number of palindromes*/
printf("Here we reached the aim at last!\n");
}
long re(long int a) /*Find the inverse number of input integer*/
{
long int t;
for(t=0;a>0;a/=10) /*Inverse the integers*/
t=t*10+a%10;
return t;
}
int nonres(long int s) /*Judge whether the given integer is a palindrome number*/
{
if(re(s)==s) return 1; /*If it is a number of palindromes, return 1*/
else return 0; /* Otherwise return 0*/
}
86. Automatic card deal
There are 52 cards in a deck of poker, and the cards should be distributed to four people when playing bridge. Please design a program to complete the automatic licensing work. Requirements: Spades are represented by S (Spaces); hearts are represented by H (Hearts); squares are represented by D (Diamonds); plum blossoms are represented by C (Clubs).
*Problem analysis and algorithm design
According to the regulations on playing bridge, each person should have 13 cards. When handing out cards, first shuffle the cards, and then send the shuffled cards to each person in a certain order. In order to facilitate computer simulation, the manual card dealing process can be modified: first determine the order of dealing: 1, 2, 3, 4; number the 52 cards in sequence: Spade 2 corresponds to the number 0, Red 2 corresponds to the number 1, Square 2 corresponds to the number 2, Plum Blossom 2 corresponds to the number 3, Spade 3 corresponds to the number 4, Red 3 corresponds to the number 5,... Then draw cards randomly from the 52 cards for each person.
Here we use the random functions of the C library function to generate a total of 52 random numbers between 0 and 51 to produce the effect of reshuffle cards.
*Program and program comments
#include<>
#include<>
int comp(const void *j,const void *i);
void p(int b[],char n[]);
int main(void)
{
static char n[]={'2','3','4','5','6','7','8','9','T','J','Q','K','A'};
int a[53],b1[13],b2[13],b3[13],b4[13];
int b11=0,b22=0,b33=0,b44=0,t=1,m,flag,i;
while(t<=52) /*Control 52 cards*/
{
m=rand()%52; /*Capplication of random numbers between 0 and 51*/
for(flag=1,i=1;i<=t&&flag;i++)/*Search for if the newly generated random number already exists*/
if(m==a[i]) flag=0; /*flag=1: The generated new random number flag=0: The newly generated random number already exists*/
if(flag)
{
a[t++]=m; /*If a new random number is generated, it will be stored in the array*/
if(t%4==0) b1[b11++]=a[t-1]; /*Judge the current value of t*/
else if(t%4==1) b2[b22++]=a[t-1]; Which array should the card of /* be stored in*/
else if(t%4==2) b3[b33++]=a[t-1];
else if(t%4==3) b4[b44++]=a[t-1];
}
}
qsort(b1,13,sizeof(int),comp); /*Sort each person's cards*/
qsort(b2,13,sizeof(int),comp);
qsort(b3,13,sizeof(int),comp);
qsort(b4,13,sizeof(int),comp);
p(b1,n); p(b2,n); p(b3,n); p(b4,n); /*Print each person's cards separately*/
return 0;
}
void p(int b[],char n[])
{
int i;
printf("\n\006 "); /*Print spade mark*/
for(i=0;i<13;i++) /*Convert the value in the array to the corresponding suit*/
if(b[i]/13==0) printf("%c ",n[b[i]%13]); /*The card corresponding to this suit*/
printf("\n\003 "); /*Print the red peach mark*/
for(i=0;i<13;i++)
if((b[i]/13)==1) printf("%c ",n[b[i]%13]);
printf("\n\004 "); /*Print square mark*/
for(i=0;i<13;i++)
if(b[i]/13==2) printf("%c ",n[b[i]%13]);
printf("\n\005 "); /*Print the plum blossom mark*/
for(i=0;i<13;i++)
if(b[i]/13==3||b[i]/13==4) printf("%c ",n[b[i]%13]);
printf("\n");
}
int comp(const void *j,const void *i) /*sort call sorting function*/
{
return(*(int*)i-*(int*)j);
}
87. Black and white subscription exchange
There are three white and three black spots arranged as shown in the following figure:
○ ○ ○ . ● ● ●
The purpose of the game is to exchange the positions of white and black spots in the above picture with the minimum number of steps:
● ● ● . ○ ○ ○
The rules of the game are: (1) Only one piece can be moved at a time; (2) The piece can be moved into a space, or skipped an opponent's piece into a space, but it cannot jump backwards, nor can it skip two pieces. Please use a computer to implement the above game.
*Problem analysis and algorithm design
The key to solving problems like this is to find out the rules of the problem, or to formulate a set of rules for computer actions. Analyzing this question, first employing people to solve the problem, you can summarize the following rules:
(1) The black spider jumps to the left and falls into the space, turn (5)
(2) White Sword jumps to the right and falls into space, turn (5)
(3) The black piece moves to the left and falls into a space (but the chess piece blocking should not occur), turn (5)
(4) The white piece moves to the right and falls into a space (but the chess piece should not be blocked and cute), turn (5)
(5) Determine whether the game is over. If it is not over, then turn (1) to continue.
The so-called "blocking" phenomenon is that during the process of moving the chess pieces, two chess pieces of the same color that have not yet been in place are connected together, making it impossible for other chess pieces in the chessboard to continue to move. For example, move the chess piece according to the following method:
0
○ ○ ○ . ● ● ●
1 ○ ○ . ○ ● ● ●
2 △ ○ ○ ● ○ . ● ●
3
○ ○ ● . ○ ● ●
4 Two ● are connected together to create blockage
○ ○ ● ● ○ . ●
Or 4 two whites are connected together to create blockage
○ . ● ○ ○ ● ●
The reason for the blockage is that in step 2 (△ state), the chess piece ○ cannot move to the right, but can only move ● to the left.
To summarize the reasons for blockage, when the chessboard appears in "black, white, empty, black" or "white, empty, black, white", the chess piece in the middle cannot be moved left or right, and only the chess piece on both sides.
According to the above rules, it can be ensured that the chess piece cannot move during the process of moving the piece, and the position exchange between the white piece and the black piece can be completed with the minimum number of steps.
*Program description and comments
#include<>
int number;
void print(int a[]);
void change(int *n,int *m);
int main()
{
int t[7]={1,1,1,0,2,2,2}; /*Initialize array 1: white sub 2: black sub 0: space*/
int i,flag;
print(t);
while(t[0]+t[1]+t[2]!=6||t[4]+t[5]+t[6]!=3) /*Judge whether the game is over?
If the exchange of chess pieces has not been completed, the loop continues*/
{
flag=1; /*flag mark for moving one step for the chess piece 1: The chess piece has not been moved 0: The chess piece has been moved*/
for(i=0;flag&&i<5;i++) /*If the white zi can skip the black zi to the right, the white zi will jump to the right*/
if(t[i]==1&&t[i+1]==2&&t[i+2]==0)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<5;i++) /*If the blackspot can jump over the whitespot to the left, the blackspot will jump to the left*/
if(t[i]==0&&t[i+1]==1&&t[i+2]==2)
{change(&t[i],&t[i+2]); print(t); flag=0;}
for(i=0;flag&&i<6;i++) /*If you move the white sub to the right, it will not cause blockage, then the white sub to the right*/
if(t[i]==1&&t[i+1]==0&&(i==0||t[i-1]!=t[i+2]))
{change(&t[i],&t[i+1]); print(t);flag=0;}
for(i=0;flag&&i<6;i++) /*If moving the blackspot to the left will not cause blockage, the blackspot will move to the left*/
if(t[i]==0&&t[i+1]==2&&(i==5||t[i-1]!=t[i+2]))
{ change(&t[i],&t[i+1]); print(t);flag=0;}
}
}
void print(int a[])
{
int i;
printf("No. %2d:………………………..\n",number++);
printf(" ");
for(i=0;i<=6;i++)
printf(" | %c",a[i]==1?'*':(a[i]==2?'@':' '));
printf(" |\n ………………………..\n\n");
}
void change(int *n,int *m)
{
int term;
term=*n; *n=*m; *m=term;
}
* Further discussion of the problem
The rules in this question not only apply to the situation of three chess pieces, but can also be generalized and apply to the situation of any N chess pieces. Readers can programmatically verify that the number of move steps of the chess piece obtained according to this rule is the smallest.
In fact, making rules is the key to solving such problems. A game program "The level of thinking depends entirely on the quality of the rules of use."
*Thoughts
There are two white and two black spots arranged as shown in the left picture:
○ . ○
. . .
● . ●
The chess pieces in the chessboard walk according to the "horse steps" rule, requiring the minimum number of steps to exchange the positions of the white and black pieces in the figure. The final result is shown in the following figure.
● . ●
. . .
○ . ○
88. The ever-winning general
There are 21 matches, and two people take turns to take them. Each person can take 1 to 4 matches each time. They cannot take more, nor can they not take no matter who takes the last match. Whoever takes the last match will lose. Please write a program to play a human-computer game, requiring the human to take it first and the computer to take it later; the computer side is the "eternal victory general".
*Problem analysis and algorithm design
When the computer is behind, in order to make the computer a "ever-winning general", it is necessary to find the key. According to the requirements of this question, the sum of the number of children taken by one party after another and the number of children taken by the other party just took by one step is equal to that, so the last son is guaranteed to be left to the person who took the son first.
Based on this analysis, algorithm design is very simple, and programming is also very easy.
*Program description and comments
#include<>
int main()
{
int a=21,i;
printf("Game begin:\n");
while(a>0)
{
do{
printf("How many stick do you wish to take(1~%d)?",a>4?4:a);
scanf("%d",&i);
}while(i>4||i<1||i>a); /*Receive the exact input*/
if(a-i>0) printf(" %d stick left in the pile.\n",a-i);
if((a-i)<=0)
{
printf(" You have taken the last stick.\n");
printf(" * * * You lose! \nGame Over.\n"); /*Output win mark*/
break;
}
else
printf(" Compute take %d stick.\n",5-i); /*Output the number of subs taken by the computer*/
a-=5;
printf(" %d stick left in the pile.\n",a);
}
}
*Thoughts
If the number of matches in the question is changed (such as 22), the side that goes back may not be able to maintain constant victory, and may change to "often defeat". At this time, the winner of the next side is directly related to the initial number of matches and the maximum number of matches allowed to be taken each time. Please write a program to solve this problem.
89. Grab 30
This is a game among Chinese folks. Two people start to report numbers in turn from 1, each person can report one number or two consecutive numbers at a time. Whoever reports 30 first will be the winner.
*Problem analysis and algorithm design
This question is similar to the previous question, and the algorithm is also similar. The difference is that the first step is optional. If the computer takes the first step, then the computer must be the winner. If a person takes one step first, the computer has to wait for the person to make mistakes. If a person takes the first step first and does not make mistakes, the person will win; otherwise the computer will seize a mistake in a person and make itself a winner.
*Program description and comments
#include<>
#include<>
#include<>
int input(int t);
int copu(int s);
int main()
{
int tol=0;
printf("\n* * * * * * * *catch thirty* * * * * * * \n");
printf("Game Begin\n");
randomize(); /*Initialize the random number generator*/
if(random(2)==1) /*Take a random number to determine which machine or person takes the first step*/
tol=input(tol); /*If it is 1, then Yu Yuan will take the first step*/
while(tol!=30) /*Game end condition*/
if((tol=copu(tol))==30) /*The computer takes a number, if it is 30, the machine will win*/
printf("I lose! \n");
else
if((tol=input(tol))==30) /*People take a number, if it is 30, the person will win*/
printf("I lose! \n");
printf(" * * * * * * * *Game Over * * * * * * * *\n");
}
int input(int t)
{
int a;
do{
printf("Please count:");
scanf("%d",&a);
if(a>2||a<1||t+a>30)
printf("Error input,again!");
else
printf("You count:%d\n",t+a);
}while(a>2||a<1||t+a>30);
return t+a; /*Return the current accumulated sum of the number that has been taken*/
}
int copu(int s)
{
int c;
printf("Computer count:");
if((s+1)%3==0) /*If the modulus of the remaining number is 1, then take 1*/
printf(" %d\n",++s);
else if((s+2)%3==0)
{
s+=2; /*If the modulus of the remaining number is 2, then take 2*/
printf(" %d\n",s);
}
else
{
c=random(2)+1; /* Otherwise, you will randomly take 1 or 2*/
s+=c;
printf(" %d\n",s);
}
return s;
}
*Thoughts
Take a clever even number. There are 25 chess pieces on the table. Both sides take turns to take the pieces. Each person takes at least one chess piece at a time, and up to 3 chess pieces can be taken away. Both sides took it like this until they took all the pieces. Therefore, one side in the hands of both parties must be an even number, the other side is an odd number, and the even number is the winner. Please program and implement human-computer games.
90.Moving Mountain Game
There are n mountains, and both sides of computer and human competition take turns to move the mountains. It is stipulated that the number of mountains moved each time cannot exceed K, and whoever moves the last one will lose. At the beginning of the game. The computer asks people to enter the total number of mountains (n) and the maximum number of mountains allowed to move each time (k). Then ask someone to start. After someone enters the number of mountains that need to be moved, the computer immediately prints out how many mountains it moves and prompts how many mountains it has remained. Both sides took turns moving the mountain until the last mountain was moved. The computer will show who the winner is and ask if the person wants to continue the game. If people don’t want to play anymore, the computer will count how many games they played and how they won or lost.
*Problem analysis and algorithm design
The following principles should be followed when participating in games:
1) When:
The number of remaining mountains -1 <= The maximum number of movable k is to be moved (the number of remaining mountains -1) so that the last mountain is left to people.
2) For any positive integer x, y, there must be:
0<=x%(y+1)<=y
In the case of n mountains, in order to leave the last mountain for people, the computer must control that the number of mountains should not exceed the maximum number k each time it moves, the number of mountains it should move should meet the following relationship:
(n-1)%(k+1)
If the calculation result is 0, that is, there is no remainder, it is stipulated that only 1 mountain will be moved to prevent problems after advancing.
According to this rule, the game program can be written as follows:
#include<>
int main()
{
int n,k,x,y,cc,pc,g;
printf("More Mountain Game\n");
printf("Game Begin\n");
pc=cc=0;
g=1;
for(;;)
{
printf("No.%2d game \n",g++);
printf("—————————————\n");
printf("How many mpuntains are there?");
scanf("%d",&n);
if(!n) break;
printf("How many mountains are allowed to each time?");
do{
scanf("%d",&k);
if(k>n||k<1) printf("Repeat again!\n");
}while(k>n||k<1);
do{
printf("How many mountains do you wish movw away?");
scanf("%d",&x);
if(x<1||x>k||x>n) /*Judge whether the number of mountains to move meets the requirements*/
{
printf("IIIegal,again please!\n");
continue;
}
n-=x;
printf("There are %d mountains left now.\n",n);
if(!n)
{
printf("……………I win. You are failure……………\n\n");cc++;
}
else
{
y=(n-1)%(k+1); /* Find the best number of mountain moving*/
if(!y) y=1;
n-=y;
printf("Copmputer move %d mountains away.\n",y);
if(n) printf(" There are %d mountains left now.\n",n);
else
{
printf("……………I am failure. You win………………\n\n");
pc++;
}
}
}while(n);
}
printf("Games in total have been played %d.\n",cc+pc);
printf("You score is win %d,lose %d.\n",pc,cc);
printf("My score is win %d,lose %d.\n",cc,pc);
}
*Thoughts
A game of picking stones. Divide the stones into several piles, each pile has several grains. The two parties A and B who participated in the game took turns to take any stones from any pile, and they could even take them all, but they could only be taken in one pile at a time. Some are not allowed to be taken from this pile, and some are taken from another pile. Whoever takes the last stone will win. Please program for human-computer chess
Hundreds of explanations for classic, practical and interesting programming of C/C++ language (10)
91. Human-computer number guessing game
The computer "think" a four-digit number, and ask someone to guess what the four-digit number is. After a person enters four digits, the computer first determines that several of the four digits are guessed correctly, and that the positions of the correct digits are also correct. The result is displayed and a prompt is given to people, and ask people to guess again until they guess the four digits the computer thinks.
For example: The computer "thinks" a "1234" and asks someone to guess. The possible prompts are as follows:
Integers guessed by people. Computers judge how many numbers are correct and how many positions are correct.
1122 2 1
3344 2 1
3312 3 0
4123 4 0
1243 4 2
1234 4 4
game over
Please program and implement the game. At the end of the game, it shows how many times people use a number.
*Problem analysis and algorithm design
The problem itself is clear. There is no need for a special algorithm to determine whether the numbers at the same position are the same. Just intercept the numbers at the same position and compare them. But when judging how many digits are correct, you should note that what computers think is "1123", and what people guess is "1576", then the correct number is only 1 digit.
Each digit of the number that is thought by the computer in the program is compared with the number that people guess. If two digits are the same, remember the position of the number you guessed so that the digit can only be "same" as the number corresponding to one. When the next digit is intercepted for comparison, it should no longer be compared with the number at the above position to avoid the error situation where the guessed digit is "same" as the multi-digit number in the corresponding number.
*Program description and comments
#include<>
#include<>
#include<>
int main()
{
int stime,a,z,t,i,c,m,g,s,j,k,l[4]; /*j: The correct number of digits k: The correct number of digits*/
long ltime;
ltime=time(NULL); /*l: When the numbers are the same, the correct position of the number that people guess*/
stime=(unsigned int)ltime/2;
srand(stime);
z=random(9999); /*Computer wants a random number*/
printf("I have a number with 4 digits in mind,please guess.\n");
for(c=1;;c++) /*c: guess the number of times counter*/
{
printf("Enter a number with 4 digits:");
scanf("%d",&g); /*Please guess*/
a=z;j=0;k=0;l[0]=l[1]=l[2]=l[3]=0;
for(i=1;i<5;i++) /*i: the i-th digit in the original number. The number one is the first, and the number one is the fourth*/
{
s=g;m=1;
for(t=1;t<5;t++) /*The number that people guess*/
{
if(a%10==s%10) /*If the i-th position is the same as the t-th position that people guess*/
{
if(m&&t!=l[0]&&t!=l[1]&&t!=l[2]&&t!=l[3])
{
j++;m=0;l[j-1]=t; /*If the number at this position is not "same" as other numbers*/
} /*When recording the same number, the position of the number in the guessed number*/
if(i==t) k++; /*If the position is also the same, then the counter k is added to 1*/
}
s/=10;
}
a/=10;
}
printf("You hane correctly guessed %d digits,\n",j);
printf("and correctly guessed %d digits in exact position.\n",k);
if(k==4) break; /*If all the positions are correct, then the person guesses correctly and exits*/
}
printf("Now you have correctly guessed the whole number after %d times.\n",c);
}
Now you have correctly guessed the whole number after 7 times.
*Thoughts
Guess the number game. The computer "thinks" a number and asks someone to guess. The person enters the guessed number. If the guess is correct, the game will end. Otherwise, the computer will give a prompt indicating whether the number people guessed is too large or too small. When a number has been guessed 20 times and has not been guessed, the guesser should stop the power to continue the game and exit from the program.
92. Human-computer number guessing game (2)
Turn the above game (91. Human-computer guessing game) down, ask someone to think of a four-digit integer, the computer will guess, and the person will give the computer a prompt message, and finally see how many times the computer uses to guess a person's "thinking". Please program and implement it.
*Problem analysis and algorithm design
When solving such problems, the computer's thinking process cannot have complete reasoning skills like a human. The key is to turn the process of reasoning and judgment into a mechanical process and find the corresponding rules, otherwise it will be difficult for the computer to complete the reasoning work.
Based on the analysis and understanding of the problem, the problem is simplified and the solution is divided into two steps to complete: first determine the composition of the four-digit numbers, and then determine the arrangement order of the four-digit numbers. The following rules can be listed:
1) Display four 1s, four 2s,..., four 0s respectively, and determine the composition of the four digits.
2) Generate all arrangements of four digits in sequence (switch the positions of all digits in sequence).
3) Process them separately according to the correct number entered by the person and the number of correct positions:
(Note that there is no input at this time, because if the four numbers have been determined, if 3 positions are correct, the position of the fourth number must be correct)
If typing 4: The game ends.
Determine the difference between this input and the last input
If the difference is 2: It means that the previous input must be 0, and the current input is 2. The positions of the two numbers exchanged this time are correct. Just exchange the other two unswaped numbers to end the game.
If the difference is -2: It means that the input in the previous time must be 2, and the input in this time must be 0. It means that the positions of the two numbers that have just been exchanged are wrong. Just restore the two numbers that have been exchanged and exchange the other two unswaped numbers to end the game.
Otherwise: If the correct position number entered this time is <= the correct position number of last time
Then restore the arrangement of the last four-digit numbers and control it to 3)
Otherwise: use the correct number of positions entered this time as the "correct number of positions entered last time", control to 3).
*Program description and comments
#include<>
#include<>
void bhdy(int s,int b);
void prt();
int a[4],flag,count;
int main()
{
int b1,b2,i,j,k=0,p,c;
printf("Game guess your number in mind is # # # #.\n");
for(i=1;i<10&&k<4;i++) /* Display four 1~9 respectively to determine the composition of the four numbers*/
{
printf("No.%d:your number may be:%d%d%d%d\n",++count,i,i,i,i);
printf("How many digits have bad correctly guessed:");
scanf("%d",&p); /*People input contains several digits*/
for(j=0;j<p;j++)
a[k+j]=i; /*a[]: Stores an array of determined numbers*/
k+=p; /*k: The number of determined numbers*/
}
if(k<4) /* Automatically calculate the number of packages in the four digits*/
for(j=k;j<4;j++)
a[j]=0;
i=0;
printf("No.%d:your number may be:%d%d%d%d\n",++count,a[0],a[1],a[2],a[3]);
printf("How many are in exact positions:"); /*Show four digits in sequence*/
scanf("%d",&b1); /*How many digits are there in the input of the person correctly*/
if(b1==4){prt();exit(0);} /*Four digits are correct, print the result. End the game*/
for(flag=1,j=0;j<3&&flag;j++) /*Realize the pairs of four numbers (a[j],a[k] exchange*/
for(k=j+1;k<4&&flag;k++)
if(a[j]!=a[k])
{
c=a[j];a[j]=a[k];a[k]=c; /*Exchange a[j],a[k]*/
printf("No.%d:Your number may be: %d%d%d%d\n",++count,a[0],a[1],a[2],a[3]);
printf("How many are in exact positins:");
scanf("%d",&b2); /*How many positions are correct for input*/
if(b2==4){prt();flag=0;} /*If all are correct, end the game*/
else if(b2-b1==2)bhdy(j,k); /*If the difference between the last time and this time is 2, then exchanging two elements will end*/
else if(b2-b1==-2) /*If the difference between the last time and this time is -2, it means that the exchanged (a[j], a[k]) is wrong
After restoring (a[j], a[k], you can end the game by exchanging two other elements*/
{
c=a[j];a[j]=a[k];a[k]=c;
bhdy(j,k);
}
else if(b2<=b1)
{
c=a[j];a[j]=a[k];a[k]=c; /*Recover the two numbers of exchange*/
}
else b1=b2; /*Other cases, the newly entered location information will be saved as the last location*/
}
if(flag) printf("You input error!\n"); /*The exchange result still has no result, it can only be an error in the information entered by the person*/
}
void prt() /*Print the result, end the game*/
{
printf("Now your number must be %d%d%d%d.\n",a[0],a[1],a[2],a[3]);
printf("Game Over\n");
}
void bhdy(int s,int b)
{
int i,c=0,d[2];
for(i=0;i<4;i++) /*Look for two elements except s and b*/
if(i!=s&&i!=b) d[c++]=i;
i=a[d[1>;a[d[1>=a[d[0>; a[d[0>=i; /*Exchange two elements except a[s] and a[b]*/
prt(); /*Print the result, end the game*/
flag=0;
}
* Running example
Suppose the four-digit number that people think is: 7215
Game Begin
Now guess your number in mind is # # # #.
No.1:your number may be:1111
* Further discussion of the problem
This program has the advantages of clear logical structure and simple and correct algorithms, but it lacks the necessary error protection function when receiving the input information from people. At the same time, in the third step of reasoning, the digital position information and the answers entered by people are not retained every time during the third step of reasoning. In this way, the legality check cannot be carried out for the information entered by people, that is, it is impossible to check whether the input information of people is contradictory; Tongchen cannot make full use of the previous results.
These defects can be improved, but the last problem is difficult to improve, so it is left to everyone to complete.
*Thoughts
"One-stop game". On a 3×3 board, both parties A and B abandon each other, and both parties take turns to put chess pieces on the board. If one of the boards is in a straight line (horizontal, vertical or diagonal), the party wins. Please write this game program to achieve the game between humans and machines. There are three types of results for the game: loss, win or draw.
During the programming process, please first analyze how to win in the competition and find out where the first step is to win.
93. Tower of Hannover
Around the end of the 19th century, an intellectual toy was sold in stores in Europe. There were three poles on a copper plate. The leftmost pole strung from top to bottom, from small to large, with a tower made of 64 discs. The purpose is to move all the discs on the leftmost rod to the right rod, provided that only one disc can be moved at a time, and the large disc is not allowed to be placed on the small disc.
*Problem analysis and algorithm design
This is a famous question, and it is found in almost all textbooks. Since the condition is that only one disk can be moved at a time, and the large disk is not allowed to be placed on the small disk, the number of movements of the 64 disks is:
18，446，744，073，709，551，615
This is an astronomical number, if it is possible to calculate (not output) every microsecond, it will take almost a million years. We can only find solutions to the problem and solve the Tower of Hanoi at a smaller N value, but it is difficult to solve the Tower of Hanoi with a computer.
Analyze the problem and find out the correct algorithm for moving the plate.
First consider the plate under the rod a rather than the top plate on the rod, so the task becomes:
*Move the 63 plates above to the b pole;
*Move the remaining plate on rod a to rod c;
*Move all the dishes on the b rod to the c rod.
To continue this process, we must first complete the work of moving 63 plates, 62 plates, 61 plates...
To describe the algorithm more clearly, a function movedisc(n,a,b,c) can be defined. The function of this function is to move N plates from rod A to rod B with the help of rod C. In this way, the work of moving N plates can be carried out according to the following process:
1) movedisc(n-1,a,c,b);
2) Move a plate from a to b;
3) movedisc(n-1,c,b,a)；
Repeat the above process until all the dishes are moved into place.
*Program description and comments
#include<>
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle);
int i=0;
int main()
{
unsigned n;
printf("please enter the number of disc:");
scanf("%d",&n); /*Input N value*/
printf("\tneedle:\ta\t b\t c\n");
movedisc(n,'a','c','b'); /*Move N plates from A with the help of B*/
printf("\t Total: %d\n",i);
}
void movedisc(unsigned n,char fromneedle,char toneedle,char usingneedle)
{
if(n>0)
{
movedisc(n-1,fromneedle,usingneedle,toneedle);
/*Move N-1 plates from fromneedle with toneedle*/
++i;
switch(fromneedle) /*Move a plate on fromneedle to toneedle*/
{
case 'a': switch(toneedle)
{
case 'b': printf("\t[%d]:\t%2d………>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t%2d……………>%2d\n",i,n,n);
break;
}
break;
case 'b': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<……………>%2d\n",i,n,n);
break;
case 'c': printf("\t[%d]:\t %2d……..>%2d\n",i,n,n);
break;
}
break;
case 'c': switch(toneedle)
{
case 'a': printf("\t[%d]:\t%2d<…………%2d\n",i,n,n);
break;
case 'b': printf("\t[%d]:\t%2d<……..%2d\n",i,n,n);
break;
}
break;
}
movedisc(n-1,usingneedle,toneedle,fromneedle);
/*Move N-1 plates to toneedle with the help of fromneedle*/
}
}
94. Childbirth
Once upon a time, there was a pair of longevity children. They gave birth to a pair of children every month. The newborn children grew up in two months, and began to give birth to their next generation children at the end of the second month. In this way, generations were born from generation to generation to solve the number of children.
*Problem analysis and algorithm design
The problem can be abstracted into the following mathematical formula:
Un=Un-1+Un-2
in:
n is the number of terms (n>=3). It is the famous Fibonacci odd sequence, the first few of the sequence are: 1, 1, 2, 3, 5, 8, 13, 21…
Phibona odd numbers can be processed in a program in a variety of ways. According to its general recursive formula, the most basic cycle control can be used to achieve the requirements of the question.
*Program description and comments
#include<>
int main()
{
int n,i,un1,un2,un;
for(n=2;n<3;)
{
printf("Please enter required number of generation:");
scanf("%d",&n);
if(n<3) printf("\n Enter error!\n"); /*Control the correct N value*/
}
un=un2=1;
printf("The repid increase of rabbits in first %d generation is as felow:\n",n);
printf("l\tl\t");
for(i=3;i<=n;i++)
{
un1=un2;
un2=un;
un=un1+un2; /*Use the general term formula to solve the value of N term*/
printf(i%10?"%d\t":"%d\n",un);
}
printf("\n");
}
*Run result
Please enter required number of generation: 20
The repid increase of rabbits in first 20 generation is as felow:
1 1 2 3 5 8 13 21 34 55
89 144 233 377 610 987 1597 2584 4181 6765
95. Convert Arabic numerals to Roman numerals
Convert Arabic numerals greater than 0 and less than 1000 to Roman numerals. The correspondence between Arabic numerals and Roman numerals is as follows:
1 2 3 4 5 ……
I II III IV V ……
*Problem analysis and algorithm design
The question shows the correspondence between Arabic numerals and Roman numerals. The number conversion in the question is actually a table search translation. That is, decompose the hundreds, ten, and single bits of the integer from the integer in sequence, find the corresponding rows in the table and output the corresponding characters.
*Programming and programming
#include<>
int main()
{
static char *a[][10]={"","I","II","III","IV","V","VI","VII","VIII","IX"
"","X","XX","XXX","XL","L","LX","LXX","LXXX","XCC",
"","C","CC","CCC","CD","D","DC","DCC","DCCC","CM"
}; /*Create a comparison table*/
int n,t,i,m;
printf("Please enter number:");
scanf("%d",&n); /*Input integer*/
printf("%d=",n);
for(m=0,i=1000;m<3;m++,i/=10)
{
t=(n%i)/(i/10); /*Pick the numbers of each bit in sequence from the high to the low bit*/
printf("%s",a[2-m][t]); /*Translation output through the comparison table*/
}
printf("\n");
}
*Run result
1. Please enter number:863
863=DCCCLXIII
2. Please enter number: 256
256=CCLVI
3. Please enter number:355
355=CCCLV
4. Please enter number:522
522=DXXII
5. Please enter number:15
15=XV
*Thoughts
Enter a positive integer N, generate the corresponding English numeric string and output it, for example:
1 ONE 2 TWO 3 THREE
10 TEN 11 ELEVEN
135 ONE HUNDRED THIRTY FIVE
96. Beauty pageant
At the semi-final match of the beauty pageant Grand Prix, a group of players participated in the competition. The rule of the competition was that the higher the final score, the lower the ranking. When the semi-decisions are over, the final score and final ranking must be announced on the spot in the order of the players' appearance. The players who get the same score have the same ranking and the rankings are numbered continuously, and the number of players with the same ranking is not necessary. For example:
Player serial number: 1, 2, 3, 4, 5, 6, 7
Player scores: 5, 3, 4, 7, 3, 5, 6
Then the output rankings are: 3, 1, 2, 5, 1, 3, 4
Please help the Grand Prix Organizing Committee complete the rating and ranking of the semi-finals.
*Problem analysis and algorithm design
If the problem is expressed in programming language, it is to number the integers in array A continuously from small to large, requiring no change of the order of elements in the array, and the same integers must have the same number.
Ordinary sorting methods all need to change the original order of array elements, which obviously cannot meet the requirements. To this end, an array is introduced that specifically stores rankings, and then the usual algorithm is used: find the minimum value among elements that have not yet been ranked, and process elements with the same value, and repeat this process until all elements are arranged.
*Program description and comments
#include<>
#define NUM 7 /*Define the number of people to be processed*/
int a[NUM+1]={0,5,3,4,7,3,5,6}; /* is to simply define the score of the player directly*/
int m[NUM+1],l[NUM+1]; /*m:Array of tags with compiled ranking l:Record subscript of elements of the same ranking */
int main()
{
int i,smallest,num,k,j;
num=1; /*rank*/
for(i=1;i<=NUM;i++) /*Control scanning the entire array, processing one ranking at a time*/
if(m[i]==0) /*If the ranking process has not been performed yet (that is, the first element that has not been processed has been found)*/
{
smallest=a[i]; /*Take the first unprocessed element as the current minimum value*/
k=1; /*Subscript of array l, number of people with the same name*/
l[k]=i; /*Record the subscript of the same name element with smallest score*/
for(j=i+1;j<=NUM;j++) /*From the next element, process the remaining elements*/
if(m[j]==0) /*If it is an element that has not been processed yet*/
if(a[j]<smallest) /*The fraction is less than the current minimum value*/
{
smallest=a[j]; /*, reset the minimum value*/
k=0; /*Reset the number of people with the same name*/
l[++k]=j; /*Record the subscript of the same name element*/
}
else if(a[j]==smallest) /*If the current minimum score is the same*/
l[++k]=j; /*Record element subscripts with the same name*/
for(j=1;j<=k;j++) /*Trade the elements with the same name*/
m[l[j>=num;
num++; /*Add 1*/
i=0; /*Control restart and find the next element that is not ranked*/
}
printf("Player-No score Rank\n");
for(j=1;j<=NUM;j++) /*Control output*/
printf(" %3d %4d %4d\n",j,a[j],m[j]);
}
*Run result
Player-No Score Rank
1 5 3
2 3 1
3 4 2
5 7 5
5 3 1
3 5 3
7 6 4
*Thoughts
If you change the "number of players with the same ranking in the original title, you do not need to consider the number of players with the same ranking" to "number the players' ranking according to the number of players with the same ranking", then how should you modify the program?
97. Sequences that meet specific conditions
Enter m and n (20>=m>=n>0) to find the positive integer sequence i1,i2,…,in that satisfies the following equation, such that: i1+i1+…+in=m, and i1>=i2…>=in. For example:
When n=4, m=8, the following 5 sequences will be obtained:
5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2
*Problem analysis and algorithm design
The original question can be abstracted as: decompose M into N integers, and the sum of N integers is M, i1>=i2>=…>=in. The method of decomposing integers is very low. Since the question contains "i1>=i2>=…..>=in, we can first determine that the value of the rightmost in element is 1, and then according to the conditions, the value of the previous element must be greater than or equal to the value of the current element, and constantly push forward can solve the problem. The following program allows the user to select M and N and output all sequences that meet the conditions.
*Program description and comments
#include<>
#define NUM 10 /*Maximum number of elements allowed to decompose*/
int i[NUM]; /*Array of decomposed values*/
int main()
{
int sum,n,total,k,flag,count=0;
printf("Please enter requried terms(<=10):");
scanf("%d",&n);
printf(" their sum:");
scanf("%d",&total);
sum=0; /*The sum of k elements from back to front*/
k=n; /*The element subscript being processed from back to forward*/
i[n]=1; /*Set the value of the last element to 1 as the initial value*/
printf("There are following possible series:\n");
while(1)
{
if(sum+i[k]<total) /*If the sum of the k bits afterwards is less than the specified total*/
if(k<=1) /*If the first element is about to be processed*/
{i[1]=total-sum;flag=1;} /* calculates the juxtaposition mark of the first element*/
else{
sum+=i[k–];
i[k]=i[k+1]; /* After setting the value of kth bit, k-1*/
continue; /*Continue to process other elements forward*/
}
else if(sum+i[k]>total||k!=1) /*If the sum has exceeded total or is not the first element*/
{ sum-=i[++k]; flag=0;} /*k falls backwards an element*/
else flag=1; /*sum+i[k]=total&&k=1 Then set the flag flag*/
if(flag)
{
printf("[%d]:",++count);
for(flag=1;flag<=n;++flag)
printf("%d",i[flag]);
printf("\n");
}
if(++k>n) /*k After returning an element backward, determine whether the last element has been exited*/
break;
sum-=i[k];
i[k]++; /*Experience the next decomposition*/
}
}
*Run result
Please enter requried terms(<=10):4
their sum:8
There are following possible series:
[1]: 5111
[2]: 4211
[3]: 3311
[4]: 3221
[5]: 2222
98. The Eight Queens Problem
On an 8×8 chessboard, there are 8 queens, each of which takes up one square; the queens are required to "attack" each other, that is, there cannot be two queens in the same row, the same column or the same diagonal line. Ask how many different methods are there.
*Problem analysis and algorithm design
This is an ancient and representative problem, and there are many algorithms when solving it using computers. Only one is introduced here.
Use one-dimensional arrays for processing. The subscript i of the array represents the i-th column on the board, and the value of a[i] represents the position where the queen is placed in the i-th column. For example: a[1]=5 means putting a queen in the fifth line of the first example of the chessboard.
In the program, first assume that a[1]=1, which means that the first queen is placed on the first row of the first column of the chessboard, and then tests the possible position of the queen in the second column. After finding the appropriate position, then deal with the subsequent columns. In this way, through repeated tests of each column, you can finally find out the entire placement method of the queen.
The program uses backtracking method, and refer to the program for details of the algorithm.
*Program description and comments
#include<>
#define NUM 8 /*Define the size of the array*/
int a[NUM+1];
int main()
{
int i,k,flag,not_finish=1,count=0;
i=1; /*The element being processed subscript means that the first i-1 element has met the requirements and the i-th element is being processed*/
a[1]=1; /* Assign initial value to the first element of the array*/
printf("The possible configuration of 8 queens are:\n");
while(not_finish) /*not_finish=1: Processing has not ended yet*/
{
while(not_finish&&i<=NUM) /*The processing has not been completed and the NUMth element has not been processed yet*/
{
for(flag=1,k=1;flag&&k<i;k++) /*Judge whether there are multiple queens in the same line*/
if(a[k]==a[i])flag=0;
for(k=1;flag&&k<i;k++) /*Judge whether there are multiple queens in the same diagonal*/
if((a[i]==a[k]-(k-i))||(a[i]==a[k]+(k-i))) flag=0;
if(!flag) /*If there is a contradiction that does not meet the requirements, the i-th element needs to be reset*/
{
if(a[i]==a[i-1]) /*If the value of a[i] has been catching up with the value of a[i-1]*/
{
i-; /*Return to one step and try to deal with the previous element again*/
if(i>1&&a[i]==NUM)
a[i]=1; /* When a[i] is NUM, set the value of a[i] by 1*/
else if(i==1&&a[i]==NUM)
not_finish=0; /*End when the value of the first bit reaches NUM*/
else a[i]++; /*Pick the value of a[i] next value*/
}
else if(a[i]==NUM) a[i]=1;
else a[i]++; /*Pick the value of a[i] next value*/
}
else if(++i<=NUM)
if(a[i-1]==NUM) a[i]=1; /*If the value of the previous element is NUM, a[i]=1*/
else a[i]=a[i-1]+1; /* Otherwise the value of the element is the next value of the previous element*/
}
if(not_finish)
{
++count;
printf((count-1)%3?" [%2d]: ":" \n[%2d]: ",count);
for(k=1;k<=NUM;k++) /*Output result*/
printf(" %d",a[k]);
if(a[NUM-1]<NUM) a[NUM-1]++; /*Modify the value of the second last digit*/
else a[NUM-1]=1;
i=NUM-1; /*Start to find the solution to the next sufficient condition*/
}
}
}
*Thoughts
An 8×8 international chess board with a total of 64 grids. Putting up to five queens into the board can control the entire plate, and no matter which square the opponent's chess piece is placed, it will be eaten. Please program
99. Addition of ultra-long positive integers
Please design an algorithm to complete the addition of two super-long positive integers.
*Problem analysis and algorithm design
First, we need to design a data structure to represent an ultra-long positive integer, and then we can design an algorithm.
First, we use a ring chain with header nodes to represent a non-negative super-large integer. If each number starts from the low bit, the numbers composed of every four digits from the first to the fourth, fifth to eighth bits... are placed in the first, second, and... nodes of the linked list in turn. The highest bit less than 4 bits is stored in the last node of the linked list. The value of the header node is specified as -1. For example:
The large integer "587890987654321" can be represented by the following linked list with header node header:
According to this data structure, you can start from two header nodes, add them in sequence in sequence, and then calculate the required carry and substitute them into the following operations. For specific implementation algorithms, please refer to the comments in the program.
*Program description and comments
#include<>
#include<>
#define HUNTHOU 10000
typedef struct node{ int data;
struct node *next;
}NODE; /*Define the linked list structure*/
NODE *insert_after(NODE *u,int num); /*Insert a new NODE after the u node, its value is num*/
NODE *addint(NODE *p,NODE *q); /*Complete the addition operation and return a pointer to the result *p+*q*/
void printint(NODE *s);
NODE *inputint(void);
int main()
{
NODE *s1,*s2,*s;
NODE *inputint(), *addint(), *insert_after();
printf("Enter S1= ");
s1=inputint(); /*Input is added*/
printf("Enter S2= ");
s2=inputint(); /*Input add number*/
printf(" S1="); printint(s1); putchar('\n'); /*Show added*/
printf(" S2="); printint(s2); putchar('\n'); /*Show the add number*/
s=addint(s1,s2); /*Sum*/
printf("S1+S2="); printint(s); putchar('\n'); /*Output result*/
}
NODE *insert_after(NODE *u,int num)
{
NODE *v;
v=(NODE *)malloc(sizeof(NODE)); /*Application for a NODE*/
v->data=num; /*Assignment*/
u->next=v; /*Insert a NODE after the u node*/
return v;
}
NODE *addint(NODE *p,NODE *q) /*Complete the addition operation and return a pointer to the result of *p+*q*/
{
NODE *pp,*qq,*r,*s,*t;
int total,number,carry;
pp=p->next; qq=q->next;
s=(NODE *)malloc(sizeof(NODE)); /*Create a linked list header for storing sum*/
s->data=-1;
t=s; carry=0; /*carry: carry*/
While(pp->data!=-1&&qq->data!=-1) /*None is not the header*/
{
total=pp->data+qq->data+carry; /*Sum of the corresponding bit and the previous carry*/
number=total%HUNTHOU; /*Finish the value of the part stored in the chain */
carry=total/HUNTHOU; /*calculate the carry*/
t=insert_after(t,number); /*Save part and into the s-direction chain*/
pp=pp->next; /*Pick the following adds respectively*/
qq=qq->next;
}
r=(pp->data!=-1)?pp:qq; /*Get the chain pointer that has not yet been completed*/
while(r->data!=-1) /*Train the larger number in the adder*/
{
total=r->data+carry; /*Add to carry*/
number=total%HUNTHOU; /*Finish the value of the part stored in the chain*/
carry=total/HUNTHOU; /*calculate the carry*/
t=insert_after(t,number); /*Save part and into the chain pointed to by s*/
r=r->next; /*Take the following value*/
}
if(carry) t=insert_after(t,1); /*process the last carry*/
t->next=s; /*Completed and linked list*/
return s; /*Returns the structure pointer to the sum*/
}
NODE *inputt(void) /*Input an extra-long positive integer*/
{
NODE *s,*ps,*qs;
struct number {int num;
struct number *np;
}*p,*q;
int i,j,k;
long sum;
char c;
p=NULL; /*Point to the input integer, the chain is the lowest single bit of the integer, and the tail of the chain is the highest bit of the integer*/
while((c=getchar())!='\n') /*Enter integer, receive numbers by character*/
if(c>='0'&&c<='9') /*If it is a number, save it */
{
q=(struct number *)malloc(sizeof(struct number)); /*Apply for space*/
q->num=c-'0'; /*Save a single integer*/
q->np=p; /*Create pointer*/
p=q;
}
s=(NODE *)malloc(sizeof(NODE));
s->data=-1; /*Create a table to find the chain header for extra-long positive integer*/
ps=s;
while(p!=NULL) /*Convert data in the received temporary data link to the required standard form*/
{
sum=0;i=0;k=1;
while(i<4&&p!=NULL) /*Take out the lower four digits*/
{
sum=sum+k*(p->num);
i++; p=p->np; k=k*10;
}
qs=(NODE *)malloc(sizeof(NODE)); /*Application space*/
qs->data=sum; /*Assign value, create a linked list*/
ps->next=qs;
ps=qs;
}
ps->next=s;
return s;
}
void printint(NODE *s)
{
if(s->next->data!=-1) /*If it is not a header, then output */
{
printint(s->next); /*Recursive output*/
if(s->next->next->data==-1)
printf("%d",s->next->data);
else{
int i,k=HUNTHOU;
for(i=1;i<=4;i++,k/=10)
putchar('0'+s->next->data%(k)/(k/10));
}
}
}
*Run result
*Thoughts
100. Digital Movement
At the nine points in the figure, the middle point is empty, and the remaining points are filled with numbers 1 to 8; the position of 1 to 8 is fixed. Then move the other numbers so that 1 to 8 is arranged clockwise from small to large. The movement rule is: you can only move the numbers along the line to blank points.
Please programmatically display the digital movement process.
*Problem analysis and algorithm design
To analyze the conditions in the question, it is necessary to use the middle blank grid to arrange the numbers clockwise, and during the arrangement process, you can only use blank points to move the numbers. The essence of the problem is to regard the 8 grids outside the matrix as a ring, and the 8 numbers are sorted within the ring, which is the same as the limitations required by the question, "the numbers can only be moved along the line to the blank points", so the middle spaces should be used for sorting, so the required sorting algorithm is unique.
Observe the middle point, it is the only point connected to the other 8 points, that is, it is the center point. The center point has the largest space for activity, and it can move in 8 directions. Make full use of the characteristic of the center point is the key to the success of the algorithm design.
After finding the position where 1 is, the correct position of the other numbers is fixed. We can adjust the positions of each number one by one according to the following algorithm starting from the number 2.
*Determine where the number i should be;
*Start from the position where the number i should be, and look backward to find the current position of the number i;
*If the current position of the number i is incorrect, move the number i from its current position (along the connection line) to the middle space, and free the original position; move all elements in front of the existing space backwards; until the position i should be vacant, move it into the middle space again.
Starting from the number 2, you can complete the moving sorting of all numbers.
When programming, the eight grids outside the matrix are regarded as a ring, and the first element of the ring is uncertain. If the algorithm is not designed well, a lot of effort will be spent in the program to deal with the order of elements in the ring. The 3X3 matrix in the question is represented by a one-dimensional array, and the middle element (number 4) is just a space. Another pointer array is designed to specifically record the connection relationship when the eight grids outside the pointer form a ring. Each element of the pointer array records the corresponding element subscripts of the numbers in the ring in sequence in the original array. In this way, the complex ring relationship in the original matrix is represented by the pointer array as a simple linear relationship, thus greatly simplifying the programming design.
*Program description and comments
#include<>
int a[]={0,1,2,5,8,7,6,3}; /*Pointer array. Serialize the subscript of the element forming the ring in the matrix in sequence*/
int b[9]; /* means 3X3 matrix, b[4] is a space*/
int c[9]; /*After determining the position of 1, the pointer array to adjust the ring*/
int count=0; /*Number move step counter*/
int main()
{
int i,j,k,t;
void print();
printf("Please enter original order of digits 1~8:");
for(i=0;i<8;i++)
scanf("%d",&b[a[i>);
/*Sequentially input 8 numbers outside the matrix, the order of matrix elements is controlled by element a[i] of the pointer array*/
printf("The sorting process is as felow:\n");
print();
for(t=-1,j=0;j<8&&t==-1;j++) /*Determine the location of the number 1*/
if(b[a[j>==1) t=j; /*t: record the location of the number 1*/
for(j=0;j<8;j++) /* Adjust the pointer array of the ring, set the position of the number 1 as the head of the ring*/
c[j]=a[(j+t)%8];
for(i=2;i<9;i++) /*Adjust the position of the numbers in sequence starting from 2*/
/*i: The number being processed, the correct position that i should be in the ring is i-1*/
for(j=i-1;j<8;j++) /*Search in sequence from the correct position where i should be*/
if(b[c[j>==i&&j!=i-1) /*If i is not in the correct position*/
{
b[4]=i; /*Move i to the center space*/
b[c[j>=0;print(); /*Empty the original location of i, output */
for(k=j;k!=i-1;k–) /*Transfer the numbers between the space before the correct position of i one piece in sequence*/
{
b[c[k>=b[c[k-1>; /*The number moves backward*/
b[c[k-1>=0;
print();
}
b[c[k>=i; /*Move the middle number i into the correct position*/
b[4]=0; /*Empty the middle space*/
print();
break;
}
else if(b[c[j>==i) break; /*number i in the correct position*/
}
void print(void) /*Output matrix according to format requirements*/
{
int c;
for(c=0;c<9;c++)
if(c%3==2) printf("%2d ",b[c]);
else printf("%2d",b[c]);
printf("—-%2d—-\n",count++);
}
*Run result
* Further discussion of the problem
Obviously, all the above algorithms can solve the problem, but the number of steps to move is not the least.
Pay attention to two problems in the algorithm. First: The position of the number 1 remains unchanged from beginning to end; second: The position is already the correct number under the initial situation. For example, the numbers 5 and 6, according to the algorithm, when moving other numbers, 5 and 6 have to move many times, which obviously takes a lot of steps.
For example, if the number 1 participates in the moving sorting process of other numbers and makes full use of the condition that the initial positions of numbers 5 and 6 are already correct, the moving sorting process can be greatly optimized.
*Thoughts
Please redesign the algorithm and write more optimized programs to minimize the number of steps you move.
Please design and complete the operations of subtraction, multiplication and division of two super-long positive integers