Poszukiwanie błędu w kodzie - wyznaczanie liczby na podstawie jej dzielników właściwych

0

Mam taki problem: ten kod działa, ale czasami się myli :) Czy moglibyście mi podać przykład, dla którego ten kod nie działa, żebym mógł go poprawić?

 #include <iostream>
using namespace std;
int NWD(long long int a, long long int b)
{
	int c=0;
	while (b!=0)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int NWW(long long int a, long long int b)
{
	int wynik;
	wynik=a*b/NWD(a,b);
	return wynik;
}		
int main() {

	long long int lwierszy, lliczb, wczytana, najwieksza, nww;
	cin >> lwierszy;
	for (; lwierszy!=0; lwierszy=lwierszy-1)
	{
		cin >> lliczb;
		cin >> nww;
		najwieksza=nww;
		for (lliczb=lliczb-1; lliczb!=0; lliczb=lliczb-1)
		{
			cin >> wczytana;
			if (wczytana>najwieksza) najwieksza=wczytana;
			nww=NWW(nww, wczytana);
		}
		if (nww==najwieksza)
			nww=nww*2;
		cout << nww << endl;
	}
}

Na wejściu jest ilość wierszy wejścia, w kolejnych wierszach jest liczba wszystkich dzielników właściwych liczby i wypisane te dzielniki.
Przykładowe wejście:

3
1 2
2 4 2
6 3 4 2 12 6 8 

Wyjście:

4
8
24 

Dzięki!

0

Posegreguj sobie dzielniki tak aby najmniejszy łączył się z największym, trochę większy z trochę mniejszym itd np:
6 3 4 2 12 6 8
2 * 12 = 3 * 8 = 4 * 6 = 24
Nie ważne jak widać który dzielnik pomnożysz przez który zawsze wychodzi ta sama liczba. Jeżeli ilość dzielników jest nieparzysta to wynikiem jest kwadrat środkowej liczby

0

To akurat działa, szukam przykładu, który nie działa. W tym wyniki są dobre. Robię to na tej zasadzie, że NWW dzielników właściwych tworzy tą liczbę, lub największy dzielnik tej liczby. Jeżeli tworzy największy dzielnik (NWW liczby = NWD liczby) to mnożę NWW przez 2 (najmniejsza naturalna > 1). Czy moje rozumowanie jest złe?

0

Działa Ci tylko dla liczb z parzystymi dzielnikami. Popraw kod na taki jaki mówiłem, mnożysz największy dzielnik z najmniejszym. Przykład dla którego nie działa to np 2 3 9, 3 5 25 125 itd.
2 3 9 -> 3 * 9 = 27 (w twoim programie 18)
3 5 25 125 -> 5 * 125 = 25 * 25 = 625 (w twoim programie 250).
Wróć uwagę jak zapisuję, dla parzystej liczby dzielników to jest iloczyn największego i najmniejszego, dla nieparzystej liczby dzielników to to samo, lub po prostu kwadrat liczby środkowej.

0

"Liczba naturalna a jest właściwym dzielnikiem n, wtedy gdy n jest wielokrotnością a oraz a nie jest równe 1 lub n. Dane są wszystkie właściwe dzielniki liczby n nie większej niż 1000000."
Dla (2, 3, 9) 18 to właściwa odpowiedź - nie ma mniejszej liczby, która dzieliłaby się przez wszystkie wymienione, a 18 nie jest równe 9. Więc wyjście jest ok.

Te long longi w sumie dużo nie wnoszą, usunąłem dla czytelności:

#include <iostream>
using namespace std;
int NWD(int a, int b)
{
	int c=0;
	while (b!=0)
	{
		c=a%b;
		a=b;
		b=c;
	}
	return a;
}
int NWW(int a, int b)
{
	int wynik;
	wynik=a*b/NWD(a,b);
	return wynik;
}		
int main() {

	int lwierszy, lliczb, wczytana, najwieksza, nww;
	cin >> lwierszy;
	for (; lwierszy!=0; lwierszy=lwierszy-1)
	{
		cin >> lliczb;
		cin >> nww;
		najwieksza=nww;
		for (lliczb=lliczb-1; lliczb!=0; lliczb=lliczb-1)
		{
			cin >> wczytana;
			if (wczytana>najwieksza) najwieksza=wczytana;
			nww=NWW(nww, wczytana);
		}
		if (nww==najwieksza)
			nww=nww*2;
		cout << nww << endl;
	}
} 
0

Czym w przykładzie (2,3,9) jest liczba 2?
Jeżeli ilością dzielników, to wyjściem powinno być 27, jeśli dzielnikiem, to wejście jest błędne. Nie istnieje liczba, dla której zbiór wszystkich dzielników to {2,3,9}.

0
merlinnot napisał(a)

Na wejściu jest ilość wierszy wejścia, w kolejnych wierszach jest liczba wszystkich dzielników właściwych liczby i wypisane te dzielniki.
Przykładowe wejście:
3
1 2
2 4 2
6 3 4 2 12 6 8

Wyjście:
4
8
24

z tego wywnioskowałem, że:
3 - ilosc liczb które będę chciał otrzymać
1 - ilość dzielników, 2- dzielnik (2 * 2 = 4 - OK)
2 - ilość dzielników, 4, 2 - dzielniki (2 * 4 = 8 - OK)
6 - ilość dzielników, 3, 4, 2, 12, 6, 8 - dzielniki (2 * 12 = 24 - OK)

Dla moich przykładów
2 - ilosc liczb które będę chciał otrzymać
2 - ilość dzielnikow, 3, 9 - dzielniki (18 - ŹLE) [27]
3 - ilość dzielników, 5, 25, 125 - dzielniki (250 - ŹLE) [625]

0

Teraz załapałem... to muszę jakoś zmodyfikować ten fragment:

 if (nww==najwieksza)
			nww=nww*2;
		cout << nww << endl;

To przez co powinien mnożyć? Przez najmniejszy wspólny dzielnik wszystkich liczb większy od 1?

0

Przeczytaj wszystkie moje posty jeszcze raz.
To co Ci tam wychodzi mnożysz przez 2, tylko dla liczb, które posiadają 2 jako dzielnik i w tym miejscu wykonujesz dokładnie to co ja powiedziałem, czyli mnożysz najmniejszy dzielnik z największym. Dla 3 i 5 będzie to mnożenie tak samo, nie 5 * 2 (jak to jest u Ciebie) tylko 5 * 3 = 15

0

Skąd wziąłeś zadanie. Czy masz gwarancje, że dane wejściowe będą poprawne? Trafiasz na wiersz 3 2 3 5. Powinny być trzy dzielniki równe 2,3,5, ale takiej liczby nie ma. Co powinien wtedy zrobić Twój program?

0

Dane na pewno są poprawne, innym osobom zaliczyło. Stworzyłem cos takiego, ale już dla przykładowego daje zły wynik:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  
int main() {
 
        int wczytana, lliczb, lwierszy;
        vector<int>lista;
        cin >> lwierszy;
        for (; lwierszy!=0; lwierszy=lwierszy-1)
        {
        	cin >> lliczb;
                for (; lliczb!=0; lliczb=lliczb-1)
                {
                cin >> wczytana;
                lista.push_back(wczytana);
                }
                sort(lista.begin(), lista.end());
                if (lista.size()%2==0) 
                	cout << (lista.front()*lista.back()) << endl;
                else
                	cout << lista[lista.size()/2]*lista[lista.size()/2]<< endl;
        }
} 
0

cout << lista[lista.size()/2]*lista[lista.size()/2]<< endl;

Powinno być:

cout << lista[lista.size() / 2 + 1] * lista[lista.size() / 2 + 1]<< endl;

Proste przykład
5 dzielników
5 / 2 = 2, a przecież chodziło nam o 3

1

Chodziło nam o trzeci element, a numerację zaczynamy od 0, więc lista[2] wskazuje na trzeci element.

1

Nie czyścisz listy

        int wczytana, lliczb, lwierszy;

        cin >> lwierszy;
        for (; lwierszy!=0; lwierszy=lwierszy-1)
        {
            vector<int>lista;
1

if (lista.size()%2==0)

Prawdę mówiąc ten warunek w ogóle nie jest potrzebny, bo przecież jeżeli masz 2 4 8, to to jest to samo 2 * 8, co 4 * 4

0

Dzięki chłopaki. Poprawione przeszło najcięższe próby :)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;  
int main() {
 
        int wczytana, lliczb, lwierszy;
        cin >> lwierszy;
        for (; lwierszy!=0; lwierszy=lwierszy-1)
        {
        	vector<int>lista;
                cin >> lliczb;
                for (; lliczb!=0; lliczb=lliczb-1)
                {
                        cin >> wczytana;
                        lista.push_back(wczytana);
                }
                sort(lista.begin(), lista.end());
                cout << (lista.front()*lista.back()) << endl;
        }
}  
0

Znacznie ładniej teraz wygląda ten main ;]

1 użytkowników online, w tym zalogowanych: 0, gości: 1