catalogue
Number of A 1
Title Description
Enter a positive integer of type int and calculate the number of 1 when the int data is stored in memory.
input
Enter an integer (type int).
output
After this number is converted to binary, the number of 1 is output.
Sample input Copy
5
Sample output: Copy
2
Analysis: according to the meaning of the question, to convert to binary is actually equivalent to the sum of how many powers of 2.
For example: 5 = 4 + 1; Is the power of 2 and the power of 0 of 2.
For example: 7 = 4 + 2 + 1;
Then, through the law, it is found that they are always equal to the sum of the largest power 2 of themselves.
For example: 5 ， then this power 2 ， is 4
For example: 7} 4
For example, 10 is 8
wait;
We just need to add the largest quadratic power of each time.
For example, a complete addition operation, such as {7 That is: first find the largest power 2 less than or equal to 7 = 4;
Then ， 7-4 = 3, and then find the maximum power 2 of ， less than or equal to 3 = 2;
Then ＾ 3-2 = 1, and then find the maximum power 2 of ＾ less than or equal to 1 = 1;
Then 1-1 = 0, which is 0.
So to sum up, 4 + 2 + 1 = 7, that is, 3 1
Similarly, the same is true for more int numbers.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int count=0;
int main (){
int n;
while(~scanf("%d",&n)){
solve(n);
printf("%d",count);
printf("\n");
count=0;
}
return 0;
}
void solve (int n){
if(n==0) return;
int z=digui(n);
z=n-z;
count++;
solve(z);
}
int digui(int x){
if(x==1) return 1;
return digui(x/2)*2;
}B minimum prime pair
Title Description
Any even number (greater than 2) can be composed of two prime numbers. There are many cases of the two prime numbers that make up the even number. This topic requires to output the prime pair with the smallest difference between the two prime numbers that make up the specified even number.
input
Enter an even number.
output
Output two prime numbers.
Sample input: Copy
20
Sample output: Copy
7
13
Analysis: according to the meaning of the question, the first step is to find two numbers. When the prime numbers are added together, they can be equal to themselves.
Write a prime function to determine whether it is a prime.
Find the intermediate value of this integer, and then search} two prime numbers from large to small, and output them directly.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int main (){
int n;
while(~scanf("%d",&n)){
solve(n);
}
return 0;
}
void solve (int n){
int mid =n/2;
for(int i=mid;i>=2;i--)
if(sushu(i)&&sushu(n-i)) {
printf("%d\n%d",i,n-i);
printf("\n");
return;
}
}
int sushu(int x){
for(int i=2;i<=sqrt(x);i++)
if(x%i==0) return 0;
return 1;
}C has a simple question
Title Description
Enter an integer n composed of four numbers. Your task is to count how many methods there are. Just modify a number and turn it into a complete square (you can't change the first number to 0). For example, if n=7844, there are two methods: 3844 = 622 and 7744 = 882.
input
Enter the first line integer t (1 < = T < = 1000), that is, the number of groups of test data. After that, each line contains an integer n (1000 < = n < = 9999).
output
For each group of data, the output just modifies a number to change n into a complete square number
Sample input: Copy
2
7844
9121
Sample output: Copy
Case 1: 2
Case 2: 0
Analysis: for this problem, you should first think about how many times you need to recurse. Obviously, it is} 4 times. Each recursion needs to be modified 10 or 9 times.
If the first bit cannot be 0, we will modify 1-9 and other bits 0-9 Just use a for loop.
Another thing, we should pay attention to whether the number itself can be squared. If so, we have to subtract 4 from the number obtained after recursion.
Because every time you recurse, you will calculate more squares including yourself.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int count=0;
int main (){
int number[4];
int n;
int t;
int temp;
while(~scanf("%d",&t)){
int x=1;
for(int i=0;i<t;i++)
{
scanf("%d",&n);
for(int i=0;i<4;i++)
{
temp=n/pow(10,3-i);
number[i]=temp%10;
}
solve(number,0);
if(check(n)) printf("Case %d: %d",x,count-4);
else printf("Case %d: %d",x,count);
printf("\n");
x++;
count=0;
}
}
return 0;
}
void solve (int number[],int a){
if(a<4){
int i=0;
int temp=number[a];
if(a==0) i=1;
for(;i<=9;i++)
{
number[a]=i;
int sum=suan(number);
if(check(sum)) count++;
}
number[a]=temp;
solve(number,a+1);
}
}
int suan (int number[]){
int sum=0;
for(int i=0;i<4;i++)
sum+=number[i]*pow(10,3-i);
return sum;
}
int check(int x){
for(int i=32;i<=99;i++)
if(i*i==x) return 1;
return 0;
}
m coloring of D-graphs
Title Description
Given undirected connected graphs, G and m have different colors. The vertices of graph G are colored with these colors, and each vertex has a color. Whether there is a shading method to make the 2 vertices of each edge in G have different colors, please output the shading scheme.
input
The first input line contains n, m and k, respectively representing n nodes, m edges and k colors. The next M lines have 2 numbers of u, v means there is an undirected edge between u and v, and there may be a self ring edge, so please ignore the self ring edge.
output
All different shading schemes are output, and the schemes are output from small to large in dictionary order.
Sample input: Copy
3 3 3
1 2
1 3
2 3
Sample output: Copy
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Analysis: first, judge how many times to recurse and how many times to recurse at several points
We recurse just to give some color.
I don't talk nonsense about anything else, that is, recursion and pruning.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int graph[200][200];
int colors[200];
int n,m,k;
int main (){
int u;
int v;
while(~scanf("%d %d %d",&n,&m,&k)){
for(int i=0;i<m;i++)
{
scanf("%d %d",&u,&v);
graph[u-1][v-1]=1;
graph[v-1][u-1]=1;
}
solve(0);
}
return 0;
}
void solve(int t){
if(t>=n){
for(int i=0;i<n;i++)
printf("%d ",colors[i]);
printf("\n");
}
else{
for(int i=1;i<=k;i++)
if(check(t,i)){
colors[t]=i;
solve(t+1);
}
}
}
int check(int t,int i){
for(int j=0;j<t;j++)
if(graph[t][j]==1&&colors[j]==i) return 0;
return 1;
}Queen E N
Title Description
The backtracking method is used to solve the post-N problem
input
Number of queens
output
Each scheme and total number of schemes
Sample input: Copy
4
Sample output: Copy
0 1 0 0
0 0 0 2
3 0 0 0
0 0 4 0
----------------
0 0 1 0
2 0 0 0
0 0 0 3
0 4 0 0
----------------
Total number of schemes: 2
Analysis: I won't talk about this kind of backtracking problem. It involves recursion. It's not very easy to talk about it. It's better to draw by yourself.
Don't be stunned by me.
Look at the code and draw a recursive tree.
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int count=0;
int n;
int m[200];
int l[200];
int r[200];
int a[200][200];
int main (){
while(~scanf("%d",&n)){
int z=solve(0);
printf("The total number of schemes is:%d",count);
}
return 0;
}
int solve(int i){
for(int j=0;j<n;j++)
{
if(!m[j]&&!l[i+j]&&!r[i-j+n]) {
a[i][j]=i+1;
m[j]=l[i+j]=r[i-j+n]=1;
if(i==n-1){
print();
count++;
printf("----------------\n");
}
else
solve(i+1);
a[i][j]=0;
m[j]=l[i+j]=r[i-j+n]=0;
}
}
return count;
}
void print(){
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
printf("%d ",a[i][j]);
if(j==n-1) printf("\n");
}
}F prime ring
Title Description
Existing 1,2,3, n. These arrays are required to form a ring so that the sum of two adjacent integers is prime. You are required to find these possible rings.
input
Enter a positive integer n.
output
When outputting, start from integer 1 and output counterclockwise. The same ring is output only once, and the rings that meet the conditions shall be output from small to large in dictionary order.
Note: each ring starts with 1.
Sample input: Copy
6
Sample output: Copy
1 4 3 2 5 6
1 6 5 2 3 4
Analysis: I won't analyze it. It's similar to map coloring.
Handwritten code
Code implementation: c language
#include <stdio.h>
#include <stdlib.h>
int number[200];
int n;
int main (){
number[0]=1;
while(~scanf("%d",&n)){
solve(1);
}
return 0;
}
void solve (int t){
if(t>=n){
if(sushu(1+number[n-1])==1){
for(int i=0;i<n;i++)
printf("%d ",number[i]);
printf("\n");
}
}
else{
for(int i=2;i<=n;i++)
{
number[t]=i;
if(check(t))
solve(t+1);
}
}
}
int check(int t){
for(int i=0;i<t;i++)
if(sushu(number[t-1]+number[t])==0||number[t]==number[i]) return 0;
return 1;
}
int sushu(int x){
if(x==1) return 0;
for(int i=2;i<=sqrt(x);i++)
if(x%i==0) return 0;
return 1;
}