VPF::Антифакториал длинного числа.

alexey009

Дата 3.10.2010, 13:29 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 60
Регистрация: 28.7.2008

Репутация: нет
Всего: 2

Полный текст задачи:

Цитата

Для любого натурального числа n, произведение 1*2*...*n называется n-факториал и обозначается n!. Требуется найти n при заданном n!
Вход. Одна строка, содержащая значение n!. Количество десятичных знаков не превышает 255. Ведущие нули отсутствуют.
Выход. Одна строка, содержащая число n.

Моя программа вываливается при вводе 1307674368000 (это 14!).
Знаю почему так происходит - следущее число 355687428096000 (это 15!) отличается от предыдущего на 2 порядка, поэтому программа неверно выставляет конец строки.
Подскажи, пожалуйста, в каком направлении капать?

Код


#include <stdio.h>
#include <string.h>

void sum(char* N, char* M) {
  int MLen = strlen(M);
  int i = 0, j = 0;
  int dec = 0;
  int ostatok = 0;
  for(i = 0; i < MLen; i++) {
    if(N[j]) {
      dec = (M[i] - '0') + (N[j] - '0') + dec;
      ostatok = dec%10;
      dec = dec/10;
      j++;
    } else {
      dec = (M[i] - '0') + dec;
      ostatok = dec%10;
      dec = dec/10;
    }
    N[i] = '0' + ostatok;
  }
  if(dec != 0)
    N[MLen] = '0' + dec;
}

void mult(char *N, char j) {
  int NLen = strlen(N);
  char Mult[500], MultFor[500];
  int Mult1, i, f, k;
  int MultLen = 0;
  int Number = 0;
  int Order = 0;
  int Ostatok;
  int OrderFor;
  for(i = 0; i < NLen; i++)
    Mult[i] = '0';
  Mult[NLen] = 0;
  for(i = NLen - 1; i >= 0; i--) {
    Mult1 = (N[i] - '0') * j;

    Number = Mult1;
    while(Number != 0) {
      Number /= 10;
      MultLen++;
    }

    for(k = 1; k <= Order; k++) {
      MultFor[k-1] = 0 + '0';
    }

    Ostatok = Mult1;
    for(f = k - 1; f < (k + MultLen - 1); f++) {
      OrderFor = Ostatok % 10;
      Ostatok = Ostatok / 10;
      MultFor[f] = OrderFor + '0';
    }
    MultFor[f] = 0;

    sum(Mult, MultFor);

    MultLen = 0;
    Order += 1;
    Mult[NLen + 1] = 0;
  }
  int len = strlen(Mult)-1;
  char t;
  int ToC = 0;
  int Center = len%2;
  if(Center == 1)
    Center = (len+1)/2;
  else
    Center = (len)/2;
    
  while(ToC < Center) {
    t = Mult[ToC];
    Mult[ToC] = Mult[len];
    Mult[len] = t;
    len--;
    ToC++;
  }
  strcpy(N, Mult);
}

int com(char *x, char *y, int NumLen) {
  int i;
  int Len1 = strlen(x);
  if(Len1 == NumLen)
    for(i = 0; i < Len1; i++) {
      if(x[i] != y[i])
        return 0;
    }
  else
    return 0;
  return 1;
}

int main() {

  unsigned char i;
  char j[255];
  char num[255];
  j[0] = '1';
  j[1] = 0;

  scanf("%s", num);
  int NumLen = strlen(num);

  for(i = 1; i <= 255; i++) {
    mult(j, i);
    if(com(j, num, NumLen) == 1) {
      printf("%d\n", i);
      return 0;
    }
  }
  return 0;
}

Это сообщение отредактировал(а) alexey009 - 3.10.2010, 13:30

JackYF

Дата 3.10.2010, 15:36 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 6
Всего: 162

Цитата(alexey009 @ 3.10.2010, 12:29

)

Знаю почему так происходит

Цитата(alexey009 @ 3.10.2010, 12:29

)

Подскажи, пожалуйста, в каком направлении капать?

Исправь, что бы не происходило. Что-то я не понял вопроса.

--------------------

Пожаловаться на меня как модератора можно здесь.

Леопольд

Дата 3.10.2010, 16:50 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 3
Всего: 13

Цитата(alexey009 @ 3.10.2010, 13:29

)

в каком направлении капать?

сверху - вниз... smile

--------------------

вопросов больше чем ответов

Void

Дата 3.10.2010, 16:57 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 2
Всего: 173

На самом деле, для решения этой задачи в такой постановке совсем не нужна длинная арифметика. Хинт: модульная арифметика.

Добавлено @ 17:09

Цитата(alexey009 @ 3.10.2010, 15:29

)

1307674368000 (это 14!).
355687428096000 (это 15!)

Между прочим, это 15! и 17!, соответственно.

В общем, как-то так:

Код

#include <stdio.h>

/* Делитель должен быть подобран так, чтобы ни одна операция 
 * не вызвала переполнение целочисленного типа. Поскольку максимальный 
 * факториал, который помещается в 255 цифр — 146!, простое число 
 * должно быть не более (2^31 - 1) / 146.
 */
#define PRIME 10000019

int main(void)
{
    char input[256];
    char *s = input;
    int modval = 0, modfac = 1;
    int i;
    
    fgets(input, sizeof(input), stdin);
    while (*s >= '0' && *s <= '9')
    {
        modval = modval * 10 + (*s - '0');
        modval %= PRIME;
        ++s;
    }
    
    for (i = 1; modfac != modval; ++i)
    {
        modfac *= i;
        modfac %= PRIME;
    }
    printf("%d\n", i - 1);
    
    return 0;
}

Отсутствие коллизий гарантировать нельзя (?), но они очень маловероятны. При заданных здесь значениях их нет.

Это сообщение отредактировал(а) Void - 3.10.2010, 17:21

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »