Алгоритм суммы цифр предыдущих чисел в С#
У меня есть последовательность чисел: 0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10... Каждое число является суммой отдельных цифр предыдущих элементов. Это немного похоже на Фибоначчи.. Я хочу написать функцию
int FindSimilarFibo(int x)
{
//x = 10 return 10
//x = 6 return 8
}
Я написал это, но я не могу понять правильный алгоритм:
int FindSimilarFibo(int x) {
int p = 0;
int q = 1;
for (int i = 0; i < n; i++)
{
int temp = p;
p = q;
q = temp + q;
if (q > 9)
{
int leftQ = q % 10;
int rightQ = q / 10;
q = leftQ + rightQ;
q = temp + q;
}
if (p > 9)
{
int leftQ = q % 10;
int rightQ = q / 10;
temp = leftQ + rightQ;
p = q;
q = temp + q;
}
}
return p;
}
@YashGupta Я ввожу индекс в указанной последовательности в функцию, и она возвращает это число.
@Cesc, если честно, это не делает его алгоритмом поиска; нет... ищите
Я отредактировал заголовок, чтобы лучше соответствовать теме, действительно, ничего общего с поиском, кроме того, что это алгоритм
Хорошо, приношу извинения за вводящую в заблуждение маркировку.
Примечание: эта последовательность достигает цикла очень быстро - начиная с n=3 существует цикл длиной 24, т.е. он перезапускается на n=27, n=51, n=75 и т. д.; поэтому, если вы хотите, вы можете реализовать это с предварительно вычисленным небольшим массивом и проверкой модуля - или версией, предложенной BurnsBA.
Ответы 3
Проблема заключается в том, что вы перезаписываете предыдущие значения при вычислении суммы цифр следующего; так... не делай этого? возможно:
static int FindSimilarFibo(int n)
{
int p = 0;
int q = 1;
for (int i = 0; i < n; i++)
{
var next = SumDigits(p) + SumDigits(q);
p = q;
q = next;
}
return p;
static int SumDigits(int value)
{
int sum = 0;
while (value > 9)
{
sum += value % 10;
value /= 10;
}
return sum + value;
}
}
Я бы посоветовал избегать таких операторов, как += и особенно /=, поскольку они кажутся очень неестественными для начинающих :) Также стоит отметить, что это решение работает и для чисел больше 99.
@mikus IMO, цель совершенно ясна - это не совсем суперэкзотический нишевый синтаксис, такой как какой-то индексатор ref-return - это основной часто используемый синтаксис, так что ... я не думаю, что мы должны стесняться показать это кому-нибудь
@MarcGravell Спасибо, я тоже думаю, что это ясно и ясно.
ну, я бы сказал... давайте адаптируем стиль к уровню вопроса :D
Если вы ищете свою последовательность в онлайн-энциклопедии целочисленных последовательностей, вы найдете ее по адресу A010077.
Одна реализация дается как
a(n) = floor(a(n-1)/10) + floor(a(n-2)/10) + (a(n-1) mod 10) + (a(n-2) mod 10)
Или в С#
public int A010077(int n)
{
int n_2 = 0;
int n_1 = 1;
int value = 0;
if (n == 0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
for (int i=0; i<n-1; i++)
{
value = (n_1 / 10) + (n_2 / 10) + (n_1 % 10) + (n_2 % 10);
n_2 = n_1;
n_1 = value;
}
return value;
}
Например
Enumerable.Range(1, 20).Select(A010077)
дает
1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6
Если вы распечатаете все значения этой последовательности, вы увидите следующее:
0, 1, 1, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10, 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10
Проверка показывает, что последовательность повторяется, начиная с 2, 3, 5, 8 и заканчивая 10, 9, 10, 10.
Учитывая это, мы можем написать решение без цикла следующим образом:
public static int FindSimilarFibo(int x)
{
if (x == 0)
return 0;
if (x <= 2)
return 1;
int[] values = { 2, 3, 5, 8, 13, 12, 7, 10, 8, 9, 17, 17, 16, 15, 13, 10, 5, 6, 11, 8, 10, 9, 10, 10 };
return values[(x + values.Length - 3) % values.Length];
}
Как это алгоритм поиска? Что именно вы ищете?