FilmProgramowanie w C++. Badanie własności liczb całkowitych. Suma dzielników liczby

Film prezentuje zagadnienie złożoności czasowej algorytmu na przykładzie badania własności liczb całkowitych, a konkretnie badania sumy dzielników danej liczby.

Ćwiczenie 0

Zdefiniuj funkcję czy_parzysta(int n), której wynikiem jest 1 w przypadku, gdy liczba podana jako parametr jest parzysta, lub 0, gdy jest nieparzysta. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji czy_parzysta(1) jest 0.
  • Wynikiem funkcji czy_parzysta(2) jest 1.

Wskazówka
Zauważ, że algorytm sprawdzania parzystości liczby opiera się na badaniu reszty z dzielenia liczby przez 2. Jeśli ta reszta równa jest 0, to liczba jest parzysta, w przeciwnym wypadku – nieparzysta.

#include <iostream> using namespace std; bool czy_parzysta(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji czy_parzysta(8) jest 1
return czy_parzysta(8)==1;
1
czy_parzysta(8)
Wynikiem funkcji czy_parzysta(13) jest 0
return czy_parzysta(13)==0;
0
czy_parzysta(13)
Wynikiem funkcji czy_parzysta(2468086420) jest 1
return czy_parzysta(2468086420)==1;
1
czy_parzysta(2468086420)
Rozwiąż ćwiczenie

Ćwiczenie 1Czy liczba jest pierwsza?

Zdefiniuj funkcję logiczną czy_pierwsza(int n), której parametrem jest liczba naturalna n większa od 1, a wynikiem wartość 1, gdy jest ona liczbą pierwszą, albo 0, gdy nią nie jest. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji czy_pierwsza(11) jest 1.
  • Wynikiem funkcji czy_pierwsza(99) jest 0.
#include <iostream> using namespace std; bool czy_pierwsza(int n) { int d = 2; while (d * d <= n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji czy_pierwsza(2) jest 1
return czy_pierwsza(2)==1;
1
czy_pierwsza(2)
Wynikiem funkcji czy_pierwsza(15555) jest 0
return czy_pierwsza(15555)==0;
0
czy_pierwsza(15555)
Wynikiem funkcji czy_pierwsza(7) jest 1
return czy_pierwsza(7)==1;
1
czy_pierwsza(7)
Rozwiąż ćwiczenie

Ćwiczenie 2N-ta liczba pierwsza

Zdefiniuj funkcję pierwsza(int n), której parametrem będzie liczba naturalna n, a wynikiem – n-ta liczba pierwsza. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji pierwsza(7) jest 17.
  • Wynikiem funkcji pierwsza(25) jest 97.
#include <iostream> using namespace std; int pierwsza(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji pierwsza(1) jest 2
return pierwsza(1)==2;
2
pierwsza(1)
Wynikiem funkcji pierwsza(17) jest 59
return pierwsza(17)==59;
59
pierwsza(17)
Wynikiem funkcji pierwsza(100) jest 541
return pierwsza(100)==541;
541
pierwsza(100)
Rozwiąż ćwiczenie

Ćwiczenie 3Liczby bliźniacze

Liczby bliźniacze to liczby pierwsze różniące się o 2. W pierwszej setce jest osiem par takich liczb: 3 i 5, 5 i 7, 11 i 13, 17 i 19, 29 i 31, 41 i 43, 59 i 61, 71 i 73. Zdefiniuj funkcję blizniacze(int n), której parametrem jest liczba naturalna n, a wynikiem pierwsza liczba z n-tej pary liczb bliźniaczych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji blizniacze(3) jest 11.
  • Wynikiem funkcji blizniacze(7) jest 59.
#include <iostream> using namespace std; int blizniacze(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji blizniacze(1) jest 3
return blizniacze(1)==3;
3
blizniacze(1)
Wynikiem funkcji blizniacze(2) jest 5
return blizniacze(2)==5;
5
blizniacze(2)
Wynikiem funkcji blizniacze(10) jest 107
return blizniacze(10)==107;
107
blizniacze(10)
Rozwiąż ćwiczenie

Ćwiczenie 4Suma dzielników liczby

Zdefiniuj funkcję suma_dzielnikow(int n), której parametrem jest liczba naturalna n, a wynikiem – suma dzielników tej liczby. Sformułuj dwa algorytmy i porównaj szybkość działania każdego z nich dla różnych danych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji suma_dzielnikow(7) jest 8.
  • Wynikiem funkcji suma_dzielnikow(25) jest 31.
#include <iostream> using namespace std; int suma_dzielnikow(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji suma_dzielnikow(2) jest 3
return suma_dzielnikow(2)==3;
3
suma_dzielnikow(2)
Wynikiem funkcji suma_dzielnikow(5) jest 6
return suma_dzielnikow(5)==6;
6
suma_dzielnikow(5)
Wynikiem funkcji suma_dzielnikow(100) jest 217
return suma_dzielnikow(100)==217;
217
suma_dzielnikow(100)
Rozwiąż ćwiczenie

Ćwiczenie 5Liczby zaprzyjaźnione

Liczby zaprzyjaźnione to dwie liczby naturalne, z których każda jest równa sumie dzielników właściwych drugiej liczby, np. 220 i 284, 1184 i 1210, 2620 i 2924. Zdefiniuj funkcję zaprzyjaznione(int n), której parametrem będzie liczba naturalna n, a wynikiem – mniejsza liczba z n-tej pary liczb zaprzyjaźnionych. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji zaprzyjaznione(1) jest 220.
  • Wynikiem funkcji zaprzyjaznione(3) jest 2620.
#include <iostream> using namespace std; int zaprzyjaznione(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji zaprzyjaznione(5) jest 6232
return zaprzyjaznione(5)==6232;
6232
zaprzyjaznione(5)
Wynikiem funkcji zaprzyjaznione(10) jest 66928
return zaprzyjaznione(10)==66928;
66928
zaprzyjaznione(10)
Wynikiem funkcji zaprzyjaznione(22) jest 196724
return zaprzyjaznione(22)==196724;
196724
zaprzyjaznione(22)
Rozwiąż ćwiczenie

Zadanie 1Liczby czworacze

Liczby czworacze to liczby pierwsze mające postać: n, n + 2, n + 6 i n + 8, np. 5, 7, 11, 13 i 11, 13, 17, 19 i 101, 103, 107, 109. Zdefiniuj funkcję czworacze(int n), której parametrem będzie liczba naturalna n, a wynikiem – pierwsza liczba z liczb czworaczych, większa od podanego parametru. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji czworacze(9) jest 11.
  • Wynikiem funkcji czworacze(150) jest 191.
#include <iostream> using namespace std; int czworacze(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji czworacze(1) jest 5
return czworacze(1)==5;
5
czworacze(1)
Wynikiem funkcji czworacze(5) jest 11
return czworacze(5)==11;
11
czworacze(5)
Wynikiem funkcji czworacze(100) jest 101
return czworacze(100)==101;
101
czworacze(100)
Rozwiąż ćwiczenie

Zadanie 2Problem Collatza

Ciąg liczb Collatza zdefiniowany jest następująco: pierwsza liczba ciągu jest dowolną liczbą naturalną x, a każda kolejna wartość ciągu obliczana jest na podstawie poprzedniej według poniższych zasad:

  • jeśli poprzednia wartość była parzysta, to należy podzielić ją przez 2;
  • jeśli poprzednia wartość była nieparzysta, to należy pomnożyć ją przez 3 i dodać 1.

Wobec tego dla wartości początkowej x = 10 kolejne liczby to: 5, 16, 8, 4, 2, 1. Zdefiniuj funkcję collatz(int x), której parametrem będzie liczba naturalna x, czyli wartość początkowa ciągu liczb Collatza, a wynikiem – liczba kroków, po których w ciągu pojawi się liczba 1. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji collatz(10) jest 6.
  • Wynikiem funkcji collatz(15) jest 17.
#include <iostream> using namespace std; int collatz(int x) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji collatz(1) jest 0
return collatz(1)==0;
0
collatz(1)
Wynikiem funkcji collatz(2) jest 1
return collatz(2)==1;
1
collatz(2)
Wynikiem funkcji collatz(20) jest 7
return collatz(20)==7;
7
collatz(20)
Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 1

Zdefiniuj funkcję parzyste(int liczba1, int liczba2), której parametrami są liczby całkowite dodatnie, przy czym liczba1 < liczba2, a ich różnica wynosi co najmniej 3. Wynikiem funkcji jest suma dwóch liczb – najmniejszej liczby parzystej większej od parametru liczba1 i największej liczby parzystej mniejszej od parametru liczba2. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji parzyste (4, 9) jest 14.
  • Wynikiem funkcji parzyste (9, 12) jest 20.
  • Wynikiem funkcji parzyste (14, 75) jest 90.
#include <iostream> using namespace std; int parzyste(int liczba1,int liczba2) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji parzyste(1, 9999) jest 10000
return parzyste(1, 9999)==10000;
10000
parzyste(1, 9999)
Wynikiem funkcji parzyste(89898, 89901) jest 179800
return parzyste(89898, 89901)==179800;
179800
parzyste(89898, 89901)
Wynikiem funkcji parzyste(10, 1000000) jest 1000010
return parzyste(10, 1000000)==1000010;
1000010
parzyste(10, 1000000)
Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 2

Zdefiniuj funkcję nieparzyste(int n), której wynikiem jest liczba liczb nieparzystych podzielnych przez 7 nie większych od parametru n. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji nieparzyste(30) jest 2.
  • Wynikiem funkcji nieparzyste(35) jest 3.
  • Wynikiem funkcji nieparzyste(100) jest 7.
#include <iostream> using namespace std; int nieparzyste(int n) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji nieparzyste(300) jest 21
return nieparzyste(300)==21;
21
nieparzyste(300)
Wynikiem funkcji nieparzyste(999) jest 71
return nieparzyste(999)==71;
71
nieparzyste(999)
Wynikiem funkcji nieparzyste(987621) jest 70544
return nieparzyste(987621)==70544;
70544
nieparzyste(987621)
Rozwiąż ćwiczenie

Ćwiczenie dodatkowe 3

Zdefiniuj funkcję dwie(int liczba), której wynikiem jest suma cyfry jedności i dziesiątek powiększona o 1, gdy jest liczbą nieparzystą, lub zmniejszona o 1, gdy jest liczbą parzystą. Parametr liczba przyjmuje wartości z zakresu od 10 do 1 000 000. Sprawdź działanie funkcji dla podanych poniżej parametrów.

  • Wynikiem funkcji dwie(1284456) jest 12.
  • Wynikiem funkcji dwie(892339) jest 11.
#include <iostream> using namespace std; int dwie(int liczba) { //zdefiniuj funkcję i sprawdź jej działanie
Wynikiem funkcji dwie(11) jest 1
return dwie(11)==1;
1
dwie(11)
Wynikiem funkcji dwie(1221) jest 4
return dwie(1221)==4;
4
dwie(1221)
Wynikiem funkcji dwie(3488677) jest 13
return dwie(3488677)==13;
13
dwie(3488677)
Rozwiąż ćwiczenie
Ta strona wykorzystuje pliki cookies w celu zapewnienia wygody przy korzystaniu z pełnej funkcjonalności. Więcej informacji