This is the 8th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021.

preface

👩🏻💻 This series is based on a certain language foundation (C, C++, Java, etc.) and basic data structure foundation for algorithm learning column, if feel a little difficult 😥, it is recommended to understand the premise knowledge before learning oh! This column will use easier to understand the expression to learn the algorithm, if there is a problem in some expressions please also give advice 🧑🏻🚀, if you feel good remember to click 👍 this column shortcut door: 🏻…

Daffodil number problem:

There is a more classic problem, is the daffodil number problem, in simple terms, a three-digit number, the cube sum of each digit is equal to itself, such as 153=1^3+5^3+3^3

Case1: Now requires the output of all daffodils in the m and N ranges

Algorithm analysis:

First, daffodil must be a three-digit number, so the range of data is naturally [100,999]. We know that each number is a three-digit number, so we just need to set a, B and C equal to three numbers respectively, and then find out whether their cubic sum is equal to the three-digit number. If so, it is the number of daffodil. You just enumerate all the numbers in this interval, count the number of daffodils.

The algorithm is as follows:

main(){
	int m,n,I,a,b,c,d=0,k;
    while(cin>>m>>n){
    if(n<m){ i=n; n=m; m=i; }}for(i=m,d=0; i<=n; i++){ a=i%10;// Retrieve the ones bit
        b=(i/10) %10;// Take the tens place
        c=i/100;// Retrieve the hundreds place
        
        if(a*a*a+b*b*b+c*c*c=i){
            d++;
        }
        
    for(i=m,k=0; i<=n; i++){ a=i%10;// Retrieve the ones bit
        b=(i/10) %10;// Take the tens place
        c=i/100;// Retrieve the hundreds place
        }   
        
        if(a*a*a+b*b*b+c*c*c=i){ cout<<i; k++;if(k<d){
            cout<<""; }}if(d==0){
            cout<<"no"<<endl; }}}Copy the code

The number of questions

Definition of completion: A positive integer greater than 1 is complete if the sum of its factors is equal to itself. For example, 6 =1+2+3 is a factor of 6, and the sum of the factors is also equal to 6. For example, 28=1+2+4+7+14

Case2: Checks the number of completions between two positive integers

Algorithm analysis:

Enumerating the number of completions within 1-10000 according to the preprocessing set, and then using each number ANS [I] to store the number of completions within 1-i, so that we can directly judge the number of completions within a certain interval. For example, the interval [a, b] would be ans [b] -ans [a-1].

Algorithm design:

#define mm 1009
int ans[mm]

bool is_ok(int m){

int sum=0;
int ms=(int) sqrt((float)m)+1;//o Enumerates every factor of m except 1
for(int i=2; i<ms; i++){if(m%i==0){
    sum+=i+m/i;
    }
    sum++;// If the sum of all factors is equal to the number m, then m is complete
if(sum==m){

return true;

}eles{
return false;
	}
  }
}

main(){
ans[1] =1;//ans[I] specifies the number of completions from 1 to I
for(int i=1; i<10000; i++){if(is_ok(i))
ans[i]=ans[i-1] +1;
else ans[i]=ans[i-1];

int cas,a,b;
	cin>cas;
while(cas--){
	cin>>a>>b;
if(a>b){
	int z;
	z=b;
	a=b;
	b=z;
		}
	cout<<ans[b]-ans[a-1]; }}Copy the code

In fact, this kind of problem is more of a mathematical thinking investigation, algorithm design is not difficult, but how to transform mathematical problems into the core of algorithm design, how to find the high efficiency of large-scale data processing problems, we must think more, so Rome was not built in a day.

Postscript tail

This is the end of this article. I am Zeus👩🏻🚀, an Internet low-level assembler. See you in the next article! 📖