Porównanie liczb o dużej ilości cyfr.

Question

Witam, mam zadanie, z którym są u mnie pewne trudności. Program ma wypisywać liczbę większą z dwóch podanych w systemie dziesiętnym i oddzielonych spacją. Nie byłoby w tym nic trudnego, gdyby nie to, że podawane liczby mogą mieć co najwyżej milion cyfr. Próbowałem rozwiązań z tablicami, coś w stylu rozpatrywania na przypadki, tzn. dwie tablice charów, jeżeli taka sama ilość znaków to przesuwanie wskaźników od pierwszej cyfry obydwu tablic i porównywanie ich, jeżeli jedna jest większa od drugiej to liczba w całości większa. Przed tym oczywiście zliczać liczby cyfr (znaków) w tablicach i rozstrzyganie, że ta z większą ilością cyfr(znaków) jest większa. Nie wiem czy takie podejście jest odpowiednie, to na pewno da się zrobić jakoś prościej i w sumie efektywniej.

Dziękuję, pozdrawiam.

Answer 1

Nie jest to trudne, w praktyce sprowadza się do sprawdzenia n pierwszych cyfr liczb (w obu tablicach) o takiej samej długości oczywiście. Nie widzę nic trudnego. Problem mógłby być jakbyś miał je pomnożyć czy podzielić ;) Przy mnożeniu używa się zwykle algorytmu Karacuby.

Jak masz dwie liczby (o tej samej liczbie cyfr!):

3456845345...............................................

3456476545...............................................

to od razu widać ze pierwsza jest większa :)  Przechodzisz przez tablicę do momentu kiedy napotkasz rożne cyfry i sprawdzasz która z nich jest większa i tyle. Przypadek kiedy liczby mają różna liczbę cyfr jest jeszcze bardziej trywialny.

Comments

#include "pch.h"
#include <iostream>
using namespace std;


int dlugosc(char const * s1)
{
	int licznik = 0;
	while (*s1)
	{
		licznik++;
			s1++;
	} return licznik;
}

bool wieksza(char const * s1, char const * s2)
{
	char const *s = s1;
	char const *p = s2;
	while (*s)
	{
		if (*p == '\0') return true;
		s++;
		p++;
	}  return false;


}

bool wieksza1(char const * s1, char const * s2)
{
	char const *s = s1;
	char const *p = s2;
	while (*s)
	{
		if (*s > *p) return true;
		s++;
		p++;
	} return false;


}

int main()
{
	char * s1 = new char [1000000];
	char * s2 = new char [1000000];
	cin >> s1;
	cin >> s2;;
	if (dlugosc(s1) != dlugosc(s2))
	{
		if (wieksza(s1, s2) == 1) cout << "PIERWSZA >"; else cout << "DRUGA >";
	} else  if (wieksza1(s1, s2) == 1) cout << "PIERWSZA >"; else cout << "DRUGA >";

Zastosowałem się do porady, jak to ocenicie? Wiem, że mało optymalnie, ale działa..

Answer 2

W tym zadaniu nic nie liczysz. Zakładając że obie liczby są dodatnie (nie ma problemu znaku), porównujesz najpierw długość napisów. W sposób oczywisty ten dłuższy będzie liczbą większą (zakładam że jest poprawną liczbą zapisaną w string'u).

Jedyny problem występuje w przypadku liczb o takiej samej długości string'a. Wtedy stosujesz compare które rozstrzyga czy liczby są równe, mniejsze czy większe: https://en.cppreference.com/w/cpp/string/basic_string/compare

Na marginesie.. lepiej taguj zapytania. Masz tam C a przykłady w C++. Zakładałem że chodzi o C++. Jeśli nie to strcmp(), załatwia także problem: https://en.cppreference.com/w/c/string/byte/strcmp

Comments

Dodatkowo w poleceniu na sprawdzianie było, że nie mogę użyć ww.  A podpowiedź odnośnie tagów wdrożę w życie.

---

No tak. To może przejedź na stronach które podałem do sekcji "Possible implementation". Będziesz miał rozwiązanie swojego problemu. A jeśli nie to "strcmp possible implementation" w google załatwia sprawę.