Heim > Backend-Entwicklung > C++ > Drücken Sie die Fakultät n als Summe aufeinanderfolgender Zahlen aus

Drücken Sie die Fakultät n als Summe aufeinanderfolgender Zahlen aus

WBOY
Freigeben: 2023-09-07 14:29:02
nach vorne
1431 Leute haben es durchsucht

Drücken Sie die Fakultät n als Summe aufeinanderfolgender Zahlen aus

Wir werden zwei Methoden besprechen, um herauszufinden, wie man die Fakultät einer Zahl als Summe aufeinanderfolgender Zahlen ausdrücken kann. Die erste Methode ist die direkte und einfache Methode, während wir bei der anderen Methode das Konzept der arithmetischen Progression verwenden, um sie hinsichtlich des Zeit- und Raumbedarfs weniger komplex zu machen.

Problemstellung

Bei einer gegebenen Zahl müssen wir einen Weg finden, die Fakultät der Zahl als Summe aufeinanderfolgender natürlicher Zahlen auszudrücken.

Hierbei handelt es sich um zwei unterschiedliche Funktionen –

  • Finden Sie die Fakultät einer Zahl.

  • Finden Sie die Anzahl der Möglichkeiten, wie eine Zahl als Summe aufeinanderfolgender natürlicher Zahlen ausgedrückt werden kann.

Beispiel 1

Given : Number = 3
Result: 1
Nach dem Login kopieren

Wir alle wissen, dass die Fakultät von 3 6 ist, was als 1+2+3 geschrieben werden kann, daher lautet unsere Antwort: 1-Weg.

Beispiel 2

Given: Number = 4
Result: 1
Nach dem Login kopieren

Wir alle wissen, dass die Fakultät von 4 24 ist, was als 7+8+9 geschrieben werden kann, daher lautet unsere Antwort: 1-Weg.

Methode 1

Dies ist eine einfache Methode, bei der wir zunächst die Fakultät einer Zahl ermitteln und dann die Anzahl der Möglichkeiten berechnen, wie sie als Summe aufeinanderfolgender natürlicher Zahlen ausgedrückt werden kann. Die Methode besteht darin, die Fakultät als eine Reihe der arithmetischen Länge len+1 als -

auszudrücken
Factorial of Number = p + (p+1) + (p+2) + … + (p+len) 
So, p = (Number- len*(len+1)/2)/(len+1) 
We will check for the values of len from 1 to len*(len+1)/2<Number
Nach dem Login kopieren

Wenn wir len als positive ganze Zahl erhalten, betrachten wir es als Lösung.

Beispiel

Im folgenden Beispiel versuchen wir herauszufinden, wie viele Möglichkeiten es gibt, die Fakultät einer Zahl als Summe aufeinanderfolgender Zahlen auszudrücken.

#include <bits/stdc++.h>
using namespace std;

// code for obtaining number of possible solutions
long int Number_of_solutions(long int NUMBER){
   long int counter = 0;
   for (long int len = 1; len * (len + 1) < 2 * NUMBER; len++) {
      double p = (1.0 * NUMBER - (len * (len + 1)) / 2) / (len + 1);
      if (p - (int)p == 0.0)
      counter++;
   }
   return counter;
}

// main program goes here
int main(){
   long int NUMBER = 15;
   cout << "Number of ways to write 15 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   NUMBER = 10;
   cout << "Number of ways to write 10 as a sum of consecutive numbers: ";
   cout << Number_of_solutions(NUMBER) << endl;
   return 0;
}
Nach dem Login kopieren

Ausgabe

Wenn Sie das obige C++-Programm ausführen, wird die folgende Ausgabe erzeugt:

Number of ways to write 15 as a sum of consecutive numbers: 3 
Number of ways to write 10 as a sum of consecutive numbers: 1
Nach dem Login kopieren

Methode 2: Optimierungsmethode

Dies ist ein besserer Ansatz; der oben gesehene Ansatz führt zu einem Überlauf.

Die Summe von len aufeinanderfolgenden Zahlen beginnend mit der Zahl p kann als -

geschrieben werden
sum = (p+1) + (p+2) + (p+3) … + (p+len) 
Hence, sum = (len*(len + 2*p + 1))/2
Nach dem Login kopieren

Weil Summe auch gleich Zahl ist!.

Wir können schreiben

2*Number! = (len*(len + 2*p + 1))
Nach dem Login kopieren

Anstatt alle (len, p)-Paare zu zählen, zählen wir hier alle (len, (len + 2*p + 1))-Paare. Das bedeutet, dass wir alle geordneten pf (A, B) berechnen, wobei AB=2*Zahl! Und A< B 且 A 和 B 的奇偶性不同,这意味着如果 len 是奇数,则 (len + 2*p + 1) 是偶数,如果 len 是偶数,则 (len + 2*p + 1) 是奇数。

Das heißt, wir suchen nach ungeraden Teilern von 2*Zahl! Dies ist auch der ungerade Teiler von Number!

Berechnen Sie die Anzahl der Teiler! , wir müssen die Potenzen der Primzahlen bei der Faktorisierung berechnen, die Anzahl der Teiler ist (f1 + 1)*(f2 + 1)* … *(fn + 1).

Wir werden die Formel von Legendre verwenden, um die höchste Potenz einer Primzahl in der Fakultät einer Zahl zu berechnen.

Beispiel

Der Code für diesen Ansatz ist unten angegeben -

#include <bits/stdc++.h>
using namespace std;
#define maximum 5002
vector<int> v;
void sieve(){
   bool Is_the_number_prime[maximum];
   memset (Is_the_number_prime, true, sizeof(Is_the_number_prime) );
   for (int prime = 2; prime * prime < maximum; prime++) {
      if (Is_the_number_prime[prime] == true) {
         for (int iterator = prime * 2; iterator < maximum; iterator += prime)
         Is_the_number_prime[iterator] = false;
      }
   }
   for (int prime = 2; prime < maximum; prime++)
   if (Is_the_number_prime[prime])
   v.push_back(prime);
}
long long int calculate_largest_power(long long int a, long long int b){
   long long int c = 0;
   long long int x = b;
   while (a >= x) {
      c += (a / x);
      x *= b;
   }
   return c;
}
long long int modular_mult(long long int a,
long long int b,
long long int m){
   long long int result = 0;
   a = a % m;
   while (b > 0) {
      if (b % 2 == 1)
      result = (result + a) % m;
      a = (a * 2) % m;
      b /= 2;
   }
   return result % m;
}
long long int no_of_ways(long long int n,
long long int m){
   long long int answer = 1;
   for (int iterator = 1; iterator < v.size(); iterator++) {
      long long int powers = calculate_largest_power(n, v[iterator]);
      if (powers == 0)
      break;
      answer = modular_mult(answer, powers + 1, m)%m;
   }
   if (((answer - 1) % m) < 0)
   return (answer - 1 + m) ;
   else
   return (answer - 1) ;
}
int main(){
   sieve();
   long long int n = 4, m = 7;
   cout << "Number of solutions after performing modulo with 7 is " <<no_of_ways(n, m);
   return 0;
}
Nach dem Login kopieren

Ausgabe

Wenn das obige C++-Programm ausgeführt wird, erzeugt es die folgende Ausgabe:

Number of solutions after performing modulo with 7 is 1.
Nach dem Login kopieren

Fazit

In diesem Artikel haben wir zwei verschiedene Möglichkeiten besprochen, die Fakultät einer Zahl als Summe aufeinanderfolgender natürlicher Zahlen herauszufinden.

Das obige ist der detaillierte Inhalt vonDrücken Sie die Fakultät n als Summe aufeinanderfolgender Zahlen aus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage