Нужна помощь в математике / Bignum - PullRequest
Новая
       34

Нужна помощь в математике / Bignum

1 голос
/ 29 августа 2010

Я борюсь со следующим фрагментом кода (/ challenge), и мне было интересно, как лучше всего это решить.

Псевдо-подобный код

Если я правильно понимаю код, он делает: 

var val = 1
foreach (char in firstargument):
  val = val * ((ascii)char + 27137)

if (val == 92156295871308407838808214521283596197005567493826981266515267734732800)
  print "correct"
else
  print "incorrect"

Где 'firstargument' - это аргумент, передаваемый программе, такой как: ./program 123456 ...

Фактический код 

#define _GNU_SOURCE
#include <unistd.h> 
#include <string.h>
#include <stdio.h>
#include <gmp.h>

int main(int argc, char *argv[])
{
    mpz_t val, mul, cmpval;
    char str[513];
    int n = 0;

    mpz_init(val);
    mpz_set_ui(val, 1);
    mpz_init(mul);
    mpz_init(cmpval);
    mpz_set_str(cmpval, "92156295871308407838808214521283596197005567493826981266515267734732800", 10);

    if (argc < 2)
    {
        printf("%s <string>\n", argv[0]);
        return -1;
    }

    strncpy(str, argv[1], 512);

    for (n = 0; n < strlen(str); n++)
    {
        mpz_set_ui(mul, (unsigned long)(str[n] + 27137));
        mpz_mul(val, val, mul);
    }

    if (!(n = mpz_cmp(val, cmpval)))
    {
        printf("correct.\n");
    }
    else 
    {
        printf("incorrect.\n");
    }

    return 0;
}

Ответы [ 3 ]

2 голосов
/ 31 августа 2010

Вот небольшая программа на Прологе для вычисления решений, сначала буквы с более низкими кодами ASCII. 

solve(A) :-
    number_anagram(92156295871308407838808214521283596197005567493826981266515267734732800, L),
    atom_codes(A,L).

number_anagram(N, L) :-
    number_anagram(N, 32, L).

number_anagram(1, 126, []).
number_anagram(N, C, [C|R]) :-
    N > 1,
    F is C + 27137,
    N mod F =:= 0,
    N1 is N / F,
    number_anagram(N1, C, R).
number_anagram(N, C, L) :-
    C < 126,
    C1 is C + 1,
    number_anagram(N, C1, L).

Оказывается, есть только одно решение: 

$ swipl

[...] 

?- ['number-anagram.pl'].
% number-anagram.pl compiled 0.00 sec, 1,636 bytes
true.

?- solve(A).
A = abbefhiooooorrsy ;
false.
2 голосов
/ 29 августа 2010

Я бы подошел к этому с точки зрения того, что большое число должно делиться на ((ascii)theVeryLastChar + 27137) - и попытался бы выяснить, что это за последний символ, - а затем поделить на него и обработать для второгоот последнего символа и т. д.

1 голос
/ 31 августа 2010

Я думаю, что это также известно как теорема / проблема китайского остатка.Алгоритм диогена является решением.

...