Paare x, y Gleichung verifizieren

Question

Ich habe ein Programm, wie unten bauen:

1. Benutzer gibt 3 Integers: a, b, c
2. Benutzer eine ganze Zahl n kommt, und dann n ganze Zahlen (aufsteigend, und verschiedene Zahlen)
3. Programm überprüft alle möglichen Paare (x, y) (mit x! = y) der eingegebenen Zahlen, wenn die Gleichung a x^2 + b y^2 = c überprüft und alle Paare die gedruckt werden überprüft die Gleichung.

ich das Programm als Gebrüll getan:

#include<iostream> 
using namespace std; 
int main() { 
int a,b,c,n,i,j; 
cin >> a; 
cin >> b; 
cin >> c; 
cin >> n; 
int num[n]; 
for(i=0;i<n;i++) { 
    cin >> num[i]; 
} 
for (i=0;i<n;i++) 
for (j=i+1;j<n;j++) { 
    if(a*num[i]*num[i]+b*num[j]*num[j] == c) { 
     cout << "(" << num[i] << "," << num[j] << ")"; 
    } 
    if(a*num[j]*num[j]+b*num[i]*num[i] == c) { 
     cout << "(" << num[j] << "," << num[i] << ")"; 
    } 
} 
return 0; 
} 

Ich habe es von O (n log n) mit zwei 'für' Aussagen, aber ich weiß es von O (n) durchgeführt werden konnte.

HINWEIS, DASS MEIN PROGRAMM FUNKTIONIERT UND ICH KEINE ERWARTETE AUSGABE UND MEINE AKTUELLE AUSGABE HINZUFÜGEN MUSS, WIE SIE IN DEN KOMMENTAREN SAGTEN. Ich möchte nur, dass ich O (N) nicht O (nlogn) -> Ich möchte eine optimierte Version des CODE!

Wie kann ich das tun?

Beispiel für laufende Programm: a = 1, b = 1, c = 20 dann n = 5 Dann n Zahlen: 2 3 4 9 18 Programm wird alle Paare zeigen (x, y), der überprüft die Gleichung x^2 + y^2 = 20. In diesem Fall zeigt es (2,4) und (4,2).

Vielen Dank!

Answer 1

Unter der Annahme, 0 basierten Index ...

Set i=0 
Set j=n-1 
While i<n or j>=0 
    Set sum=a(num[i]^2)+b(num[j^2) 
    If sum==c then found pair, and increase i 
    If sum<c increase i 
    If sum>c decrease j 

Answer 2

fand ich genau dieses Problem hier gelöst: http://lonews.ro/educatie-cultura/22899-rezolvare-admitere-universitatea-bucuresti-2015-pregatire-informatica.html und ein wenig verändert, die Paare zeigen (es zeigt, ursprünglich die Zahl der Paare).

#include <iostream> 
using namespace std; 

int main() 
{ 
    int a, b, c, n, i=0; 
    cout << "a = "; 
    cin >> a; 
    cout << "b = "; 
    cin >> b; 
    cout << "c = "; 
    cin >> c; 
    cout << "n = "; 
    cin >> n; 

    int s[n]; 
    for(i=0; i<n; i++) { 
     cout << "s[" << i+1 << "] = "; 
     cin >> s[i]; 
    } 
    int j=n-1; 
    i = 0; 
    while(j>=0 || i<n) { 
     if(a*s[i]*s[i] + b*s[j]*s[j] == c) { 
      cout << "(" << s[i] << "," << s[j] << ") "; 
      i++; 
     } 
     if(a*s[i]*s[i] + b*s[j]*s[j] < c) { 
      i++; 
     } 
     if(a*s[i]*s[i] + b*s[j]*s[j] > c) { 
      j--; 
     } 
    } 
    return 0; 
}