Массив: математическая последовательность - PullRequest
Новая
       11

Массив: математическая последовательность

1 голос
/ 21 марта 2010

Массив целых чисел A [i] (i> 1) определяется следующим образом: элемент A [k] (k> 1) наименьшее число больше, чем A [k-1], так что сумма его цифр равен сумме цифр числа 4 * A [k-1].

Вам нужно написать программу, которая вычисляет N-е число в этом массиве на основе заданного первого элемента A [1].

ВХОД: В одной строке стандартного ввода есть два числа, разделенных одним пробелом: A [1] (1 <= A [1] <= 100) и N (1 <= N <= 10000). </p>

ВЫВОД: Стандартный вывод должен содержать только одно целое число A [N], N-е число определенной последовательности.

Input: 7 4

Выход: 79

Пояснение: Элементы массива следующие: 7, 19, 49, 79 ... и четвертый элемент - решение.

Я пытался решить эту проблему путем кодирования отдельной функции, которая для заданного числа A [k] вычисляет сумму своих цифр и находит наименьшее число больше, чем A [k-1], как указано в задаче, но без успех. Первое тестирование не удалось из-за ограничения памяти, второе тестирование не удалось из-за ограничения времени, и теперь у меня нет никакой возможной идеи, как решить эту проблему. Один друг предложил рекурсию, но я не знаю, как это установить.

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

Ответы [ 3 ]

1 голос
/ 21 марта 2010

Это не имеет ничего общего с рекурсией и почти ничего с динамическим программированием. Вам просто нужно найти эффективные оптимизации, чтобы сделать это достаточно быстро. Просто подсказка, попробуйте понять это решение:

http://codepad.org/LkTJEILz

0 голосов
/ 21 марта 2010

Это довольно рекурсивно.

Суть проблемы:

Найдите наименьшее число N больше K, имеющее цифру (N) = J.

  • Если цифра (K) == J, проверьте, удовлетворяет ли N = K + 9 условию.

  • Если цифра (K)

  • В противном случае, если цифра (K) <= J, новая цифра равна 9, и проблема повторяется: «Найти наименьшее число N 'больше, чем (K / 10), имеющее цифру (N') = J-9 тогда N = N '* 10 + 9 ". </p>

  • Если цифра (К)> J, то ???

В каждом случае N <= 4 * K </p>

9 -> 18 по первому правилу

52 -> 55 по второму правилу

99 -> 189 по третьему правилу, первое правило используется во время рекурсии

25 -> 100 требует четвертого случая, в котором я изначально не видел необходимости.

Еще есть контрпримеры?

0 голосов
/ 21 марта 2010

Вот простое решение на python. Он использует только итерацию, рекурсия не нужна и неэффективна даже для быстрого и грязного решения. 

def sumDigits(x):
    sum = 0;
    while(x>0):
        sum += x % 10
        x /= 10
    return sum

def homework(a0, N):
    a = [a0]
    while(len(a) < N):
        nextNum = a[len(a)-1] + 1
        while(sumDigits(nextNum) != sumDigits(4 * a[len(a)-1])):
            nextNum += 1
        a.append(nextNum)
    return a[N-1]

PS. Я знаю, что на самом деле мы не должны давать ответы на домашние задания, но кажется, что OP находится во введении в класс C ++, поэтому, вероятно, еще не знает python, надеюсь, это просто выглядит как псевдокод. Также в коде отсутствует много простых оптимизаций, которые, вероятно, сделали бы его слишком медленным для решения, как есть.

...