Chapter II program design of circular structure

Catalog

2.1 for loop

②7744 problem

2.2 while Circulation and do-while loop

3n+1 problem

Approximate calculation

2.3 The cost of the cycle

Sum of factorials

2.4 Input and output framework in algorithm competition

② I / O redirection ,

④ Multiple sets of data

2.5 Notes and exercises

① Narcissistic number

② Han Xin orders soldiers

③ Inverted triangle

Equilateral triangle

④ The sum of subsequences

---

2.1 for loop

① Format ：for( initialization ; Conditions ; adjustment )

②7744 problem

floor（x） Return is no greater than x Maximum integer for ;

floor（x+0.5） rounding

#include<stdio.h>
#include<math.h>
int main(){
for(int a=1;a<=9;a++)
for(int b=0;b<=9;b++)
{
int n=a*1100+b*11;
int m=floor(sqrt(n)+0.5);
if(m*m==n)
printf("%d",n);
}

#include<stdio.h>
int main() {
	for (int x = 1; ; x++) {
		int n = x * x;
		if (n < 1000) continue;//continue Yes, jump back for The beginning of the cycle , Go straight to the next cycle 
		if (n > 9999) break;//break It's about jumping out of the loop 
		int hi = n / 100;// Top two 
		int lo = n % 100;// The last two 
		if (hi / 10 == hi % 10 && lo / 10 == lo % 10)//abcd   a=b c=d
			printf("%d\n", n);
	}
return 0;
}

2.2 while Circulation and do-while loop

Format ：while（ Conditions ） The loop body ;

3n+1 problem

For any greater than 1 The natural number of n, if n It's odd , Will n Turn into 3n+1, Otherwise it becomes n Half of . After several such transformations , It will definitely make n Turn into 1. Input n, Number of output transformations .n<=10^9.

#include<stdio.h>
int main() {
	int n2, count = 0;
	scanf("%d", &n2);
	long long n = n2;// Avoid being right long long Input and output of 
	while (n > 1)
	{
		if (n % 2 == 1)
			n = n * 3 + 1;
		else
			n /= 2;
		count++;
	}
	printf("%d", count);
	return 0;
}

Approximate calculation

π/4=1-1/3+1/5-1/7+······, Until the last item is less than 1e-6

1e-6 It means floating point numbers . That is to say 1*10 Of -6 Power .

#include<stdio.h>
int main() {
	double sum = 0;
	for (int i = 0; ; i++)
	{
		double term = 1.0 / (i * 2 + 1);
		if (i % 2 == 0)sum += term;
		else sum -= term;
		if (term < 1e-6) break;
	}
	printf("%.6f\n", sum);
	return 0;
}

2.3 The cost of the cycle

Sum of factorials

Input n, Calculation s=1！+2！+3！+……+n！ The last six （ Without leading 0）.n<=1e+6,n! Before presentation n The product of two positive integers ;

As long as the last six , Output time pair 1e+6 Take the mold .

#include<stdio.h>
int main() {
	const int MOD = 1000000;
	int n, s=0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
			int sum = 1;
			for (int j = 1; j <= i; j++) {
				sum =(sum* j%MOD);
			}
			s =(s+ sum)%MOD;
		}
		printf("%d\n", s);
	
	return 0;
}

problem ： Multiplication overflow .

The two most common problems in loop structure programming ： Arithmetic overflow and program inefficiency .

Solution ： Math knowledge

Return to the original question ,n！, if n！ At the end 6 individual 0, It does not affect the last six digits of the sum .

And when n be equal to 25 when ,25！ At the end 6 individual 0, From this item, all items will not affect the end of the sum 6 position ,

So it should be written in front of the program if(n>25) n=25;

#include<stdio.h>
int main() {
	const int MOD = 1000000;
	int n, s=0;
	scanf("%d", &n);
	if (n > 25)
		n = 25;
	for (int i = 1; i <= n; i++) {
			int sum = 1;
			for (int j = 1; j <= i; j++) {
				sum =(sum* j%MOD);
			}
			s =(s+ sum)%MOD;
		}
		printf("%d\n", s);
	return 0;
}

#include<time.h>

printf("Time used=%.2f\n",(double)clock()/CLOCK_PER_SEC);
// Get the running time of the whole program 

2.4 Input and output framework in algorithm competition

① stay Windows Next , After entering, press Enter key , Press again Ctrl+Z key , Finally, press Enter, You can end typing .

    stay Linux Next , Press... After input Ctrl+D Key to end the input .

② I / O redirection ,

stay main Add two statements at the entrance of the function . File input and output

freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

Be careful ： Understand the rules of document reading and writing before the competition , Is the standard input / output , Or file input and output , In case of file input and output , Whether to prohibit using redirection to access files .

③

// If the game requires file input and output , But redirection is prohibited , use fopen
FILE *fin,*fout;
fin=fopen("data.in","rb");
fout=fopen("data.out","wb");

fscanf(fin,"%d",&x);

fprintf(fout,"%d",x);

fclose(fin);
fclose(fout);// Close folder 
// If you want to change to standard input and output , Just assign a value "fin=stdin;fout=stdout;" that will do 

④ Multiple sets of data

Enter some data , Find the minimum 、 Maximum 、 Average （ Keep three decimal places ）. Enter to ensure that these numbers do not exceed 1000 The integer of .

The input contains multiple sets of data , The first row of each group of data is the number of integers n, The second line is n It's an integer ,n=0 Mark the end of the input , The program should ignore this set of data . A blank line should be output between two adjacent groups of data .

#include<stdio.h>
#define INF 1000000000 /* Variables are initially assigned before use , because min The minimum value is saved , The initial value should be a large number ,max By contrast , Define a large number , Make max=-INF,min=INF.*/
int main() {
	int x, n = 0, kase = 0;
	while (scanf("%d", &n) == 1 && n)//n=0 For input end flag ,&&n
	{
		int s = 0;
		int min = INF, max = -INF;
		for (int i = 0; i < n; i++) {
			scanf("%d", &x);
			s += x;
			if (x < min) min = x;
			if (x > max) max = x;
		}
		if (kase) printf("\n");
		printf("Case %d:%d %d %.3f\n", ++kase, min, max, (double)s / n);
	}
	return 0;
}

2.5 Notes and exercises

① Narcissistic number

100~999 Number of all daffodils in .

#include<stdio.h>
#include<math.h>
int main() {
    int a,b,c = 0;
    int count = 0;
    for (int i = 100; i < 1000; i++) {
        a = i / 100;// Hundred bit 
        b = (i / 10) % 10;// ten 
        c = i% 10;// bits 
        if (i == pow(a, 3) + pow(b, 3) + pow(c, 3)) {
            count++;
            if (count != 0&&count!=1) {
                printf(" ");
            }// Space to separate each group of data 
            printf("%d", i);
        }
    }
    return 0;
}

② Han Xin orders soldiers

It's said that Han Xin is very intelligent , Never count your own troops directly , Just let the soldiers line up in three 、 Five in a row 、 Seven people in a row to change the formation , And every time he glanced at the end of the line, he knew the total number of people .
Input 3 Nonnegative integers a,b,c , Indicates the number of people at the end of each formation （a<3,b<5,c<7）,
Output the minimum number of people （ Or the report doesn't explain ）. The total number of people known is not less than 10, No more than 100 .
 

③ Inverted triangle

#include<stdio.h>
int main() {
	int n = 0;
	scanf("%d",& n);
	for (int i = n; i>0; i--)
	{
		for (int k =n-i; k >0; k--) 
		{
			printf(" ");
		}
		for (int j=2*i-1 ; j >0; j--)
		{
				printf("#");
		}
		printf("\n");
	}
	return 0;
}

Equilateral triangle

#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
		for (int i = 0; i <= n; i++) 
		{
			for (int k = 0; k < n - i; k++) 
			{
				cout << " ";
			}
			for (int j = 0; j < 2 * i - 1; j++)
			{
				cout << "#";
			}
			cout << endl;
		}
}

④ The sum of subsequences

Output two positive integers n<m<1e6. Output 1/n2 + 1/(n+1)2+…+1/m2, Keep five decimal places . The end is marked as n=m=0.

#include<stdio.h>
int main() {
	int n, m = 1,kase=0,s=0;
	while (scanf("%d %d", &n, &m) && (n != 0) && (m != 0))
	{
		double sum = 0;
		for (int i = n; i <= m; i++)
		{
			sum += 1.0 / i/i;
		}
		++kase;
		printf("Case %d :%.5lf",kase ,sum);
	}
	return 0;
}