Finden pythagoreischen Triplett, für die a + b + c = 1000
https://stackoverflow.com/questions/2817848
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
A pythagoreischen Triplett ein Satz von drei natürlichen Zahlen ist, a 2 + b 2 = c 2
Beispiel 3 2 + 4 2 = 9 + 16 = 25 = 5 2 .
Es gibt genau einen pythagoreischen Triplett, für die a + b + c = 1000. Finden Sie das Produkt abc.
Quelle : http://projecteuler.net/index .php? section = Probleme & id = 9
Ich habe versucht, aber wusste nicht, wo mein Code falsch gelaufen ist. Hier ist mein Code in C:
#include <math.h>
#include <stdio.h>
#include <conio.h>
void main()
{
int a=0, b=0, c=0;
int i;
for (a = 0; a<=1000; a++)
{
for (b = 0; b<=1000; b++)
{
for (c = 0; c<=1000; c++)
{
if ((a^(2) + b^(2) == c^(2)) && ((a+b+c) ==1000)))
printf("a=%d, b=%d, c=%d",a,b,c);
}
}
}
getch();
}
Lösung
#include <math.h>
#include <stdio.h>
int main()
{
const int sum = 1000;
int a;
for (a = 1; a <= sum/3; a++)
{
int b;
for (b = a + 1; b <= sum/2; b++)
{
int c = sum - a - b;
if ( a*a + b*b == c*c )
printf("a=%d, b=%d, c=%d\n",a,b,c);
}
}
return 0;
}
Erklärung:
- b = a;
wenn a, b (a <= b) und c die pythagoreischen Triplett,
dann b, a (b> = a) und c - auch die Lösung, so dass wir nur einen Fall suchen - c = 1000 - a - b; Es ist eine der Bedingungen des Problems (wir brauchen nicht alle möglichen ‚c‘ zu scannen: nur berechnen it)
Andere Tipps
Ich fürchte ^ nicht tut, was Sie denken, es tut in C. Ihre beste Wette ist a*a für Integer-Quadrate zu verwenden.
Hier ist eine Lösung Euclid-Formel ( Link ).
Lassen Sie uns tun einige Mathe: Im allgemeinen wird jede Lösung die Form
a=k(x²-y²)
b=2kxy
c=k(x²+y²)
wobei k, x und y positive ganze Zahlen sind, y Jetzt, a + b + c = kx² +-ky² 2kxy + kx² + ky² = 2kx² + 2kxy 2kx = (x + y) = 1000 Teile durch 2: kx (x + y) = 500 Nun setzen wir s = x + y: KXS = 500 Jetzt suchen wir nach Lösungen von KXS = 500, wobei k, x und s ganze Zahlen und Sie können dies noch verbessern: Für n = 1000, so weist das Programm sechs Werte für x zu prüfen und in Abhängigkeit von den Details der Implementierung für y auf einen Wert auf. Dies wird beenden, bevor Sie die Taste loslassen. x < s < 2x sind.
Da alle von ihnen 500 teilen, können sie nehmen nur die Werte 1, 2, 4, 5, 10, 20, 25, 50, 100, 125, 250, 500. Einige dieser Pseudo-Code für beliebige n zu tun (und kann erfolgt von Hand leicht für n = 1000) If n is odd
return "no solution"
else
L = List of divisors of n/2
for x in L
for s in L
if x< s <2*x and n/2 is divisible by x*s
y=s-x
k=((n/2)/x)/s
add (k*(x*x-y*y),2*k*x*y,k*(x*x+y*y)) to list of solutions
sort the triples in the list of solutions
delete solutions appearing twice
return list of solutions
Wie bereits erwähnt, ist ^ bitweise xor, nicht Macht.
Sie können auch die dritte Schleife, entfernen und stattdessen
c = 1000-a-b; und optimieren diese ein wenig.
Pseudocode
for a in 1..1000
for b in a+1..1000
c=1000-a-b
print a, b, c if a*a+b*b=c*c
Es gibt eine ziemlich schmutzig, aber schnelle Lösung für dieses Problem. Angesichts der beiden Gleichungen
a * a + b * b = c * c
a + b + c = 1000.
Sie können ableiten, die folgende Beziehung
a = (1000 * 1000-2000 * b) / (2000-2b)
oder nach zwei einfachen mathematischen Transformationen erhalten Sie:
a = 1000 * (500-b) / (1000 - b)
da ein muss eine natürliche Zahl sein. Daher können Sie:
for b in range(1, 500):
if 1000*(500-b) % (1000-b) == 0:
print b, 1000*(500-b) / (1000-b)
Got führt 200 und 375.
Viel Glück
#include <stdio.h>
int main() // main always returns int!
{
int a, b, c;
for (a = 0; a<=1000; a++)
{
for (b = a + 1; b<=1000; b++) // no point starting from 0, otherwise you'll just try the same solution more than once. The condition says a < b < c.
{
for (c = b + 1; c<=1000; c++) // same, this ensures a < b < c.
{
if (((a*a + b*b == c*c) && ((a+b+c) ==1000))) // ^ is the bitwise xor operator, use multiplication for squaring
printf("a=%d, b=%d, c=%d",a,b,c);
}
}
}
return 0;
}
Haben Sie dies nicht getestet, aber es sollte Sie auf dem richtigen Weg gesetzt.
Von man pow:
POW(3) Linux Programmer's Manual POW(3)
NAME
pow, powf, powl - power functions
SYNOPSIS
#include <math.h>
double pow(double x, double y);
float powf(float x, float y);
long double powl(long double x, long double y);
Link with -lm.
Feature Test Macro Requirements for glibc (see feature_test_macros(7)):
powf(), powl(): _BSD_SOURCE || _SVID_SOURCE || _XOPEN_SOURCE >= 600 || _ISOC99_SOURCE; or cc -std=c99
DESCRIPTION
The pow() function returns the value of x raised to the power of y.
RETURN VALUE
On success, these functions return the value of x to the power of y.
If x is a finite value less than 0, and y is a finite non-integer, a domain error occurs, and a NaN is
returned.
If the result overflows, a range error occurs, and the functions return HUGE_VAL, HUGE_VALF, or HUGE_VALL,
Wie Sie sehen, pow wird mit Fließkommaarithmetik, bei denen es unwahrscheinlich ist, dass Sie das genaue Ergebnis geben (obwohl in diesem Fall sollte in Ordnung sein, als relativ kleine ganze Zahlen eine genaue Darstellung haben, aber verlassen Sie sich nicht auf, dass für die allgemeine Fälle) ... Verwendung n*n die Zahlen in integer-Arithmetik (auch zum Quadrat, in der modernen CPU ist mit leistungsfähigen Punkteinheiten Floating der Durchsatz in Gleitkomma noch höher sein, aber von integer zu Gleitkomma-Umwandlung hat eine sehr hohe Kosten in der Anzahl der CPU-Zyklen, so dass, wenn man es zu tun mit ganzen Zahlen, versuchen zu integer-Arithmetik zu halten).
einig Pseudo-Code zu optimieren Sie ein wenig Ihren Algorithmus Bit:
for a from 1 to 998:
for b from 1 to 999-a:
c = 1000 - a - b
if a*a + b*b == c*c:
print a, b, c
In C der Operator ^ berechnet bitweise xor, nicht die Macht. Verwenden x*x statt.
Wie andere erwähnt haben, müssen Sie den ^ Operator verstehen. Auch Ihr Algorithmus werden mehrere äquivalente Antworten mit den Parametern erzeugen a, b und c in unterschiedlicher Reihenfolge.
Während so viele Leute haben darauf hingewiesen, dass der Code in Ordnung arbeiten, sobald Sie mit pow wechseln. Wenn Ihr Interesse an etwas Mathematik Theorie lernen, wie es zu CS gilt, würde ich empfehlen, zu versuchen, eine effient Version Implementierung „Euclid-Formel“ zur Erzeugung von pythagoreischen Tripel ( link ).
ich weiß, diese Frage ist ziemlich alt, und jeder hat für Schleifen mit 3 Posting Lösungen gewesen, die benötigt wird, nicht. Ich habe dies in O (n) gelöst, durch **equating the formulas**; **a+b+c=1000 and a^2 + b^2 = c^2**
Also, die Lösung weiter wir bekommen;
a+b = 1000-c
(a+b)^2 = (1000-c)^2
Wenn wir lösen weiter Wir leiten es zu;
a = ((50000- (1000 * b)) / (1000-b)). Wir Schleife für „b“ und findet „a“.
Sobald wir "a" und "b" haben, bekommen wir "c".
public long pythagorasTriplet(){
long a = 0, b=0 , c=0;
for(long divisor=1; divisor<1000; divisor++){
if( ((500000-(1000*divisor))%(1000-divisor)) ==0){
a = (500000 - (1000*divisor))/(1000-divisor);
b = divisor;
c = (long)Math.sqrt(a*a + b*b);
System.out.println("a is " + a + " b is: " + b + " c is : " + c);
break;
}
}
return a*b*c;
}
Euclid Methode gibt den Umfang m (m + n) = p / 2, wobei m> n, und die Seiten sind m ^ 2 + n ^ 2 ist die Hypotenuse und die Beine sind 2mn und m ^ 2-n ^ zu sein 2.thus m (m + n) = 500 ergibt schnell m = 20 und n = 5. Die Seiten sind 200, 375 und 425. Die Nutzung Euklid alle pythorean primitive Fragen zu lösen.
Da es zwei Gleichungen (a+b+c = 1000 && aˆ2 + bˆ2 = cˆ2) mit drei Variablen, können wir es in linearer Zeit lösen, indem nur durch alle möglichen Werte einer Variablen Looping, und dann können wir die anderen zwei Variablen in konstanter Zeit lösen.
Von der ersten Formel, erhalten wir b=1000-a-c, und wenn wir b in der 2. Formel mit diesem ersetzen, wir c^2 = aˆ2 + (1000-a-c)ˆ2 bekommen, was das Verfahren vereinfacht zu c=(aˆ2 + 500000 - 1000a)/(1000-a).
Dann haben wir eine Schleife durch alle möglichen Werte von a, lösen c und b mit den obigen Formeln, und wenn die Bedingungen erfüllt sind, haben wir unsere Triplett gefunden.
int n = 1000;
for (int a = 1; a < n; a++) {
int c = (a*a + 500000 - 1000*a) / (1000 - a);
int b = (1000 - a - c);
if (b > a && c > b && (a * a + b * b) == c * c) {
return a * b * c;
}
}
Ich denke, der beste Ansatz hier ist diese:
int n = 1000;
unsigned long long b =0;
unsigned long long c =0;
for(int a =1;a<n/3;a++){
b=((a*a)- (a-n)*(a-n)) /(2*(a-n));
c=n-a-b;
if(a*a+b*b==c*c)
cout<<a<<' '<<b<<' '<<c<<endl;
}
Erklärung:
Wir werden an den N und A konstant beziehen, so werden wir nicht zwei Schleifen verwenden.
Wir können es tun, weil
c=n-a-b und b = (a^2-(a-n)^2)/(2(a-n))
Ich habe diese Formeln durch ein System von Gleichungen gelöst werden:
a+b+c=n,
a^2+b^2=c^2
func maxProd(sum:Int)->Int{
var prod = 0
// var b = 0
var c = 0
let bMin:Int = (sum/4)+1 //b can not be less than sum/4+1 as (a+b) must be greater than c as there will be no triangle if this condition is false and any pythagorus numbers can be represented by a triangle.
for b in bMin..<sum/2 {
for a in ((sum/2) - b + 1)..<sum/3{ //as (a+b)>c for a valid triangle
c = sum - a - b
let csquare = Int(pow(Double(a), 2) + pow(Double(b), 2))
if(c*c == csquare){
let newProd = a*b*c
if(newProd > prod){
prod = newProd
print(a,b,c)
}
}
}
}
//
return prod
}
Die Antworten oben gut genug sind, aber fehlt eine wichtige Information a + b> c . ;)
Weitere Details werden zu denen zur Verfügung gestellt werden, die fragen.
for a in range(1,334):
for b in range(500, a, -1):
if a + b < 500:
break
c = 1000 - a - b
if a**2 + b**2 == c**2:
print(a,b,c)
Eine weitere Optimierung von Oleg Antwort. Eine Seite kann nicht größer sein als die Summe aus den beiden anderen. So a + b nicht weniger als 500 sein kann
