[C] Program z dzielnikami i sumą

Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

[C] Program z dzielnikami i sumą

Post autor: Poszukujaca »

Mam do napisania program, który wczyta liczbę naturalną z klawiatury, a następnie sprawdzi, czy suma jej wszystkich dzielników (oprócz liczby jej równej) jest równa tej liczbie.
np: \(\displaystyle{ 6=1+2+3}\) - wspomniana własność liczby zachodzi
np: \(\displaystyle{ 10 \neq 1+2+5}\) - własność nie zachodzi

Program ma byc w języku c, nie c++!!!

Ktoś pomoże?

Dział "programy matematyczne" jest przeznaczony na dyskusję na temat profesjonalnych programów znajdujących zastosowanie w matematyce (np. mathcad). Wątki dotyczące programów o mniejszym stopniu skomplikowania, tworzonych przez nas, należy zamieszczać w dziale informatycznym.
Ostatnio zmieniony 12 lip 2014, o 21:49 przez Afish, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Chromosom
Moderator
Moderator
Posty: 10365
Rejestracja: 12 kwie 2008, o 21:08
Płeć: Mężczyzna
Podziękował: 127 razy
Pomógł: 1271 razy

[C] Program z dzielnikami i sumą

Post autor: Chromosom »

Dla pewnej liczby \(\displaystyle{ n}\) proponuję sprawdzić wszystkie liczby mniejsze lub równe \(\displaystyle{ \sqrt n}\). Jeśli pewna liczba \(\displaystyle{ m<\sqrt n}\) jest dzielnikiem, również \(\displaystyle{ \frac nm}\) jest dzielnikiem - do sumy należy dodać \(\displaystyle{ m+\frac nm}\). Liczba \(\displaystyle{ m}\) jest dzielnikiem, gdy \(\displaystyle{ n % m == 0}\) (zapisane programistycznie: reszta z dzielenia \(\displaystyle{ n}\) przez \(\displaystyle{ m}\) wynosi 0). W przypadku gdy \(\displaystyle{ m=\sqrt n}\) dodajemy tylko \(\displaystyle{ m}\), ponieważ \(\displaystyle{ \frac nm}\) jest wtedy tą samą liczbą.

Dodatkową optymalizację można by uzyskać, rozpatrując jedynie liczby pierwsze mniejsze lub równe \(\displaystyle{ \sqrt n}\). Jednakże złożoność byłaby tylko \(\displaystyle{ O(\log_2n)}\) razy mniejsza, co nie jest znaczącą różnicą w przypadku niewielkich \(\displaystyle{ n}\). Implementacja takiego algorytmu byłaby nieco trudniejsza.
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

[C] Program z dzielnikami i sumą

Post autor: Poszukujaca »

Chromosom, niestety nie rozumiem tego algorytmu.

Napisałam coś takiego:

Kod: Zaznacz cały

#include <stdio.h>

main()
{
	int a,i=1;
	int k;
	printf("Podaj liczbe calkowita. 
");
	scanf("%d",&a);
	printf("Dzielnikami liczby %d sa
",a);
	for(i=1;i<a;i++){
		if(a%i==0){
			printf("%d
",i);
		}
	}
}


Program ten wypisuje wszystkie dzielniki liczby oprócz dzielnika, którą jest tą liczbą. Pozostaje mi zapisać warunek na sumę dzielników i porównać ją z tą liczbą. Ale jak zapisać sumę takich dzielników? Moge wprowadzić nową zmienną i napisać zwykłe działanie, a potem użyć pętli "if" w celu sprawdzenia czy zachodzi równość między liczbą a sumą dzielników. Tylko problem tkwi w tym, jak oznaczyć te dzielniki, żeby program wiedział co ma dodać.
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

[C] Program z dzielnikami i sumą

Post autor: Andreas »

Tylko problem tkwi w tym, jak oznaczyć te dzielniki, żeby program wiedział co ma dodać.
Możesz je sumować w tym samym miejscu gdzie je wypisujesz.
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[C] Program z dzielnikami i sumą

Post autor: kalwi »

Kod: Zaznacz cały

#include <stdio.h>

int main()
{
	int liczba, dzielnik=0;
	printf("Podaj liczbe: ");
	scanf("%d", &liczba);
	for (int i = liczba / 2; i > 0; i--)
		if ((liczba%i) == 0)
			dzielnik += i;
	if (dzielnik == liczba)
		printf("Wlasnosc zachodzi.
");
	else
		printf("Wlasnosc nie zachodzi.
");
	getchar();
	getchar();
	return 0;
}
-- 13 lip 2014, o 02:24 --

Swoją drogą taka własność zachodzi dla liczb zwanych doskonałymi. Program sprawdza liczby z zakresu \(\displaystyle{ \left\langle 1;\frac{n}{2} \right\rangle}\) dla podanej liczby \(\displaystyle{ n}\) i następnie je sumuje i porównuje z podaną liczbą. Pewnie można by trochę zoptymalizować pod kątem szybkości działania, ale jak na Twój poziom to powinno być ok.

-- 13 lip 2014, o 02:26 --
Poszukujaca pisze:Napisałam coś takiego:

Kod: Zaznacz cały

main()
...
To jest niepoprawnie, main() zwraca wartość typu int.
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

[C] Program z dzielnikami i sumą

Post autor: Andreas »

Ten program można napisać dużo prościej.
Liczb doskonałych które mieszczą się w zakresie inta jest... 5.
6,
28,
496,
8128,
33550336,
8589869056,

Robimy więc tablicę 5-elementową, i potem sprawdzamy czy wczytana liczba nie jest którąś z tej tablicy. Szybkość działania: błyskawiczna.
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[C] Program z dzielnikami i sumą

Post autor: kalwi »

a co, jeśli zakresem będzie unsigned long long?
Andreas
Użytkownik
Użytkownik
Posty: 1130
Rejestracja: 1 lis 2008, o 22:33
Płeć: Mężczyzna
Podziękował: 72 razy
Pomógł: 156 razy

[C] Program z dzielnikami i sumą

Post autor: Andreas »

Wtedy trzeba będzie zrobić tablicę 8-elementową.
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[C] Program z dzielnikami i sumą

Post autor: kalwi »

Hmmm, myślałem, że będzie dużo więcej takich liczb. W takim razie to najlepszy "algorytm"
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

[C] Program z dzielnikami i sumą

Post autor: Poszukujaca »

kalwi pisze:

Kod: Zaznacz cały

#include <stdio.h>

int main()
{
	int liczba, dzielnik=0;
	printf("Podaj liczbe: ");
	scanf("%d", &liczba);
	for (int i = liczba / 2; i > 0; i--)
		if ((liczba%i) == 0)
			dzielnik += i;
	if (dzielnik == liczba)
		printf("Wlasnosc zachodzi.
");
	else
		printf("Wlasnosc nie zachodzi.
");
	getchar();
	getchar();
	return 0;
}
-- 13 lip 2014, o 02:24 --

Swoją drogą taka własność zachodzi dla liczb zwanych doskonałymi. Program sprawdza liczby z zakresu \(\displaystyle{ \left\langle 1;\frac{n}{2} \right\rangle}\) dla podanej liczby \(\displaystyle{ n}\) i następnie je sumuje i porównuje z podaną liczbą. Pewnie można by trochę zoptymalizować pod kątem szybkości działania, ale jak na Twój poziom to powinno być ok.

-- 13 lip 2014, o 02:26 --
Poszukujaca pisze:Napisałam coś takiego:

Kod: Zaznacz cały

main()
...
To jest niepoprawnie, main() zwraca wartość typu int.

Dziękuję, właśnie o to mi chodziło!

Nie rozumiem dlaczego nie mogę napisać bez funkcji. Czy moge prosić o jakieś wyjasnienie?

Chcąc zrobić trochę po swojemu, napisałam tak:

Kod: Zaznacz cały

#include<stdio.h>

main()
{
	int n, suma_dzielnikow=0;
	printf("Podaj liczbe naturalna n:
");
	scanf("%d",&n);
	
	int i;
	for(i=1;i<n;i++)
	{
		if(n%i==0)
		suma_dzielnikow+=i;
	}
	if(suma_dzielnikow==n)
	printf("Liczba jest doskonala.");
	else 
	printf("Liczba nie jest doskonala.");
}

Program działa poprawnie
kalwi
Użytkownik
Użytkownik
Posty: 1931
Rejestracja: 29 maja 2009, o 11:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 145 razy
Pomógł: 320 razy

[C] Program z dzielnikami i sumą

Post autor: kalwi »

Ponieważ standard mówi, że main() zwraca wartość typu int. Tylko dlatego i aż dlatego. W lepszych, nowszych kompilatorach taki program się nie skompiluje (np. w Visual Studio 2013, jeśli mnie pamięć nie myli).

Kod: Zaznacz cały

   for(i=1;i<=n/2;i++)
lepiej byłoby tak, przecież wiadomo, że dzielnikami liczby 6 nie mogą być 4,5,6 (yyy zgodnie z definicją liczby doskonałej).
Awatar użytkownika
Poszukujaca
Użytkownik
Użytkownik
Posty: 2775
Rejestracja: 21 maja 2012, o 23:32
Płeć: Kobieta
Podziękował: 1019 razy
Pomógł: 166 razy

[C] Program z dzielnikami i sumą

Post autor: Poszukujaca »

Poprawiłam na tak:

Kod: Zaznacz cały

#include<stdio.h>

int main()
{
	int n, suma_dzielnikow=0;
	printf("Podaj liczbe naturalna n:
");
	scanf("%d",&n);
	
	int i;
	for(i=1;i<=n/2;i++)
	{
		if(n%i==0)
		suma_dzielnikow+=i;
	}
	if(suma_dzielnikow==n)
	printf("Liczba jest doskonala.");
	else 
	printf("Liczba nie jest doskonala.");

	return 0;
}

Czy trzeba użyć tutaj getchar? Do czego służy ta komenda?
Na_ten_czas
Użytkownik
Użytkownik
Posty: 47
Rejestracja: 30 paź 2012, o 17:41
Płeć: Mężczyzna
Podziękował: 15 razy
Pomógł: 5 razy

[C] Program z dzielnikami i sumą

Post autor: Na_ten_czas »

Poszukujaca pisze:Czy trzeba użyć tutaj getchar? Do czego służy ta komenda?
Funkcja getchar pobiera znak ze standardowego wejścia. Tutaj: program nie zakończy się dopóki nie zostanie wprowadzony kolejny znak (Visual Studio domyślnie zamyka okno konsoli po wykonaniu programu).
ODPOWIEDZ