[Algorytmy] Odnalezienie brakującej cyfry

[paewel]

Witam,

Probuje napisac algorytm do odzyskiwania numeru ISBN, jezeli blednie zostala odczytana jedna z cyfr.
Wiadomo ktora cyfra jest zla, trzeba ja zamienic na odpowiednia przy uzyciu sumy kontrolnej, ktora liczy sie w nastepujacy sposob:

Kod: Zaznacz cały

978185326048 3
3 - suma kontrolna
10 - (9 * 1 + 7 * 3 + 8 * 1 (zamienie mnozymy o 1 i 3))%10 = suma kontrolna

Powiedzmy, ze przed ostatnia cyfra, 8, zostala zle odczytana, wiedzac to zostaje mi rownanie:

Kod: Zaznacz cały

10 - (83 + 3 * a) % 10 = 3

Co mozemy uproscic do

Kod: Zaznacz cały

(3 + 3 * a) % 10 = 7

No i co dalej Prosze o pomoc. Oczywiscie moglbym sprobowac podstawic kazda z cyfr of 0 do 9 i sprawdzic, czy zgadza sie suma kontrolna, ale sumienie nie pozwala mi na to

[gryxon]

Chyba podejście sprawdzenia 9 kandydatów jest lepsze niż bawienie się w rozszerzone algorytmy euklidesa (szukanie odwrotności liczb modulo \(\displaystyle{ 10}\), szczególnie, że \(\displaystyle{ 10}\) nie jest liczbą pierwszą ).

[paewel]

Dzieki Gryxon, tak wlasnie zrobie

[norwimaj]

Wystarczy wiedzieć, że \(\displaystyle{ 1^{-1}=1}\) i \(\displaystyle{ 3^{-1}=7.}\) Nie trzeba wtedy sprawdzać wszystkich możliwych cyfr.

[Chromosom]

\(\displaystyle{ 3a+3\pmod{10}=7\\ 3a\pmod{10}=4\\ 21a\pmod{10}=28\\ a\pmod{10}=8}\)

Wynik jest poprawny, chętnie jednak dowiem się, czy powyższy sposób jest błędny.

[gryxon]

A co jeżeli będzie:
\(\displaystyle{ 2a = 4 \mod{10}}\)

lub

\(\displaystyle{ 4a = 2 \mod{10}}\)

??

Albo lepiej:

\(\displaystyle{ 5a = 0 \mod{10}}\)

możliwości teraz będziemy mieć 5, które spełnią to równanie.

[norwimaj]

A co jeżeli będzie:
\(\displaystyle{ 2a = 4 \mod{10}}\)

A skąd ma się wziąć ta dwójka? Mnożymy cały czas przez jedynki i trójki. Gdyby któraś cyfra była mnożona przez \(\displaystyle{ 2,}\) to nie dałoby się jej odtworzyć.

[gryxon]

Dobra, mój błąd.

[paewel]

Dzięki Chromosom Narazie Twoje rozwiązanie przechodzi moje testy. Jakby ktoś był zainteresowany to tutaj jest kod w obj-c:

Kod: Zaznacz cały

+ (NSString *)calculateMissingDigit:(NSString *)word
{
	NSCharacterSet *nonDigitCharSet = [[NSCharacterSet decimalDigitCharacterSet] invertedSet];
	NSArray *components = [word componentsSeparatedByCharactersInSet:nonDigitCharSet];
	NSString *firstComponent = components[0];
	int letterPosition = firstComponent.length;
	int missingDigit;

	if (letterPosition == 12) {
		missingDigit = [ChecksumControll iSBN13ChecksumNumber:[word substringToIndex:word.length - 1]];
	} else {
		NSUInteger length = [word length];
		unichar buffer[length + 1];
		[word getCharacters:buffer range:NSMakeRange(0, length)];
		int rest = 0;
		for(int i = 0; i < length - 1; i++) {
			if (i != letterPosition) {
				int multiplier = i % 2 ? 3 : 1;
				rest += (buffer[i] - 48) * multiplier;
			}
		}
		int reversedCheckSum = 10 - (buffer[length - 1] - 48);
		int multiplier = letterPosition % 2 ? 7 : 1;
		int baseNumber = reversedCheckSum - rest;
		missingDigit = (multiplier * (baseNumber % 10)) % 10;
		missingDigit += missingDigit >= 0 ? 0 : 10;
	}
	NSString *fullISBN = [word stringByReplacingCharactersInRange:NSMakeRange(letterPosition, 1) withString:@(missingDigit).stringValue];
	return fullISBN;
}

Jakby było coś niezrozumiałego to proszę pisać, wiem, że obj-c nie jest bardzo popularnym językiem