Мысал. Үлкен сандардың көбейтіндісін табу.

Те үлкен сандарға амалдар қолдану есептері

Көбінесе олимпиадаларда берілетін есептер үлкен сандарды табуға арналған арифметикалық операцияларды қолдану арқылы шешіледі. Бұл есептерді шешу барысында біз алдынғы сабақта қарастырған бір өлшемді массивтер мен қатарды өңдеудің типтік алгоритмдерін пайдаланамыз.

Жұмыстың мақсаты: үлкен сандарды шығаруға арналған операцияларды қолданып классикалық әдістер арқылы есептерді шығару.

32 разрядты жүйенің архитектурасы максималды диапазондағы сандарды 0..4294967295 өңдеуге мүмкіндік береді. Бірақ көптеген қолданбалы есептерді шешу үшін бұл сандар аралығы жеткіліксіз(3.1-кесте).

Мәліметтер:

Анықтамалық мәліметтер:

3.1-кесте. Бүтін сандардың форматы
Типті сипаттау	Ұзындығы(байт)	Минималды сан	Максималды сан
Integer	2 (таңбалы)	-32768	+32767
Shortint	1 (таңбалы)	-128	+127
Longint	4 (таңбалы)	-2147483648	+2147483647
Byte	1 (таңбасыз)
Word	2 (таңбасыз)

Улкен сандарды шығару операцияларын тәжірбие жүзінде қарастырамыз.

Мысал. Өте үлкен санды бір таңбалы санға көбейту керек.

Есепті шешуін мысалмен қарастырайық: айталық, 4510905723598 санын 3-ке көбейту қажет болсын.

· Санды жолдық айнымалы арқылы ендіреміз (өйткені, берілген 1 таңбалы санды сипаттайтын бүтін тип қарастырылмаған.

· Санның цифрларын ажыратып, массив элементтеріне орналастырып жазамыз:

4 5 1 0 9 0 5 7 2 3 5 9 8

· Олардың әрқайсысын 3-ке көбейтеміз:

12 15 3 0 27 0 15 21 6 9 15 27 24

· Ауыстыруды ұйымдастырамыз: әрбір ұяшықта кіші разрядты цифрды қалдырамыз, ал үлкен разрядты цифрды сол жақтағы ұяшықта тұрған санға қосамыз.

Сурет 3.1

Паскальдағы программа үлгісі:

const m=100;var a, b: array [1..m] of integer; i, n, x, k: integer; s: string;begin writeln ('Ұзын санды енгіз: '); readln (s); n:= length (s); writeln ('Көбейткішті енгіз: '); readln (x); for i:=1 to n do val (copy(s, i, 1), a[i], k); for i:=1 to n do b[i]:= a[i] * x; for i:=n downto 2 do begin b[i - 1]:= b[i - 1] + b[i] div 10; b[i]:= b[i] mod 10; end; {нәтиже} for i:=1 to n do write (b[i]);end.

Тест:

Берілгені:
Натижесі:

2-мысал: Екі үлкен санның қосындысын табу:

Есепті шешу идеясы:екі үлкен санды қосу мысалын қарастырамыз: 4510905723569 және 361295487.

Сандарды жолдық айнымалылар арқылы ендіреміз. Әрбір санның цифрларын ажыратып алып, массив элементтеріне орналастырамыз. Екі санның кішісі сан сақталатын массивті (бұл массив b болсын) 5-ші ұяшықтан бастап толтырамыз.

Сурет 3.2

Sum массивін толтыру үшін a және b массивінің сәйкес ұяшықтарын қосамыз. Содан соң орын ауыстыруды ұйымдастырамыз: әрбір ұяшықта кіші разрядты цифрды қалдырамыз, ал үлкен разрядты цифрды сол жақтағы ұяшықта тұрған санға қосамыз.

Программаның Паскальдағы үлгісі:

const mm=100;var a,b, sum: array [1..mm] of integer; i, n, m,max, x, k: integer; sA, sB: string;begin writeln ('бірінші сан: '); readln (sA); writeln ('екінші сан: '); readln (sB); n:= length (sA); m:= length (sB); if n>m then max:=n else max:=m; for i:=1 to n do begin val(copy(sA, i, 1),x,k); a[i+(max-n)]:=x; end; for i:=1 to m do begin val(copy(sB, i, 1),x,k); b[i+(max-m)]:=x; end; {======қосу===========} for i:=1 to max do sum[i]:= a[i]+b[i]; for i:=max downto 2 do begin sum[i-1]:=sum[i-1] + sum[i] div 10; sum[i]:= sum[i] mod 10; end; {====нәтиже===========} for i:=1 to max do write (sum[i]);end.

Тест:

Берілгені:
Нәтижесі:

мысал. Үлкен сандардың көбейтіндісін табу.

Есепті шешу идеясы схемада көрсетілген (3.3-сурет):

3.3. Сурет

• b массивінің ең соңғы элементін a массивінің барлық элеметтеріне көбейтеміз. Нәтижесін Nat массивіне сақтаймыз;
• Sum массиві мен 1 позицияға солға жылжытылған Nat массивінің элементтерін қосамыз; Нәтижесін Sum-ға жазамыз;
• b массивінің келесі элементін (соңынан екіншісі) алып, алдыңғы екі қадамды қайталаймыз;
• экранға Sum массивін шығарамыз.

Программаның Паскальдағы үлгісі:

const mm=100;var a,b,nat,sum: array [1..mm] of integer; i, j, n, m, max, x, k: integer; sA, sB: string;begin writeln ('бірінші көбейткіш: '); readln (sA); writeln ('екінші көбейткіш: '); readln (sB); n:= length(sA); m:= length(sB); {======цифрларға бөліп алу===============} for i:= 1 to n do begin val(copy(sA, i, 1),x,k); a[i]:= x; end; for i:= 1 to m do begin val(copy(sB, i, 1),x,k); b[i]:= x; end; {== j-ші цифрға көбейту ============} for j:= m downto 1 do begin for i:= 1 to n do nat[i]:= a[i] * b[j]; for i:= n downto 2 do begin nat[i - 1]:= nat[i - 1] + nat[i] div 10; nat[i]:= nat[i] mod 10; end; {==== сырғыта отырып қосынды табу ==============} for i:= 1 to n do sum[i + j - 1]:= sum[i + j - 1] + nat[i]; for i:= n downto 2 do begin sum[i - 1]:= sum[i - 1] + sum[i] div 10; sum[i]:= sum[i] mod 10; end; end; {====нәтиже=================} for i:= 1 to n + m - 1 do write (sum[i]);end.

Тест: