вычислить последовательность

#c_sharp #алгоритм

n = 12
должно вывести 1+2+3+4+5+6+7+8+9+(1+0)+(1+1)+(1+2)
Написал 2 программы, но пишет, из-за того что долго выполняются - процесс отменяется.
То есть, их нужно оптимизировать, только вот КАК
Код двух программ:

using System;

public class TwistedSum
{
public static long Solution(long n)
{
int res = 0;
int ostatok = 0;
int Part = 0;
for (int i = 1; i <= n; i++)
  {
      if (i >=10)
      {
      Part = i;
      while (Part >= 0)
      {

          ostatok = Part % 10;
          Part = Part / 10;
          res = res + ostatok;
      }
      }
      else { res = res + i}
   }

  return res;
}
}


(тут передается в n число, все нормально, просто только функция написана)
2ой код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace codewarsSumaCifr
{
class Program
{
    static void Main(string[] args)
    {
        long n = 10;
        Console.Write(Solution(n));
        Console.ReadKey();

    }


    public static long Solution(long n)
    {
        int res = 0;
        string str2 = "";
        for (int i = 1; i <= n; i++)
            {
                str2 = str2 + i.ToString();
            }

        for (int j = 0; j < str2.Length; j++)
            {
                res = res + (int)Char.GetNumericValue(str2[j]);

            }
        return res;
    }
}
}

    

Ответы

Ответ 1

Цикл, вообще не правильное решение, его надо свернуть, и решить задачу аналитически.
Решать задачу целиком скучно, но идею, как она решается, подкину:

9:    (0+0)+(0+1)+(0+2)+(0+3)+(0+4)+(0+5)+(0+6)+(0+7)+(0+8)+(0+9) = 45
19:   (1+0)+(1+1)                          ... +(1+8)+(1+9) + 45  = 1*10 + 1*45 + 45
29:   (2+0)+(2+1)                 ... +(2+8)+(2+9) + 2*45 + 1*10  = 2*10 + 1*10 +
2*45 + 45
...
99:   (9+0)+(9+1)  ...+(9+9) + 9*45 + 8*10 ... + 1*10 = 9*10 + 8*10 ... + 1*10 +
9*45 + 45


Ответ 2

Придумал алгоритм, который вычислит намного быстрее. Вычислительная сложность предыдущего
ответа — O(n log(n)), тогда так сложность этого ответа — O(log(n)).  Вот код, объяснение
ниже. Процесс примерно так, как и в ответве Mirdin'a.

public static long Solution(long n)
{
    long sum = 0;
    long power = 1;
    while (power <= n)
    {
        long mod = n % (power * 10),
            remainder = (n - mod) / 10,
            digit = mod / power;

        sum += 45 * remainder +
            power * digit * (digit - 1) / 2 +
            digit * ((mod % power) + 1);

        power *= 10;
    }
    return sum;
}


Как это работает?

Например, как узнать Solution(62345)? Считаем по каждой цифре:


62345: (0+1+2+3+4+5+6+7+8+9)*6234 + (0+1+2+3+4) + 5
62345: (0+1+2+3+4+5+6+7+8+9)*6230 + (0+1+2+3)*10 + 4*(5+1)
62345: (0+1+2+3+4+5+6+7+8+9)*6200 + (0+1+2)*100 + 3*(45+1)
62345: (0+1+2+3+4+5+6+7+8+9)*6000 + (0+1)*1000 + 2*(345+1)
62345: (0+1+2+3+4+5)*10000 + 6*(2345+1)


Ещё замечаем, что 0+1+2+3+4+5+6+7+8+9 равно 45, и что 0+1+...+(k-1)равно k*(k-1)/2:


62345: 45*6234 + (5*4/2) + 5
62345: 45*6230 + (4*3/2)*10 + 4*(5+1)
62345: 45*6200 + (3*2/2)*100 + 3*(45+1)
62345: 45*6000 + (2*1/2)*1000 + 2*(345+1)
62345: (6*5/2)*10000 + 6*(2345+1)


В сумме, получится 1276185.


Ответ 3

Первая программа почти правильное, только у вас бесконечный цикл while (Part >= 0).
Можно делать так, немного по проще:

public static long Solution(long n)
{
    long sum = 0;
    for (long i = 1; i <= n; i++)
    {
        long j = i;
        while (j > 0)
        {
            sum += j % 10;
            j /= 10;
        }
    }
    return sum;
}


Кстати, это последовательность A037123 в OEIS.


Ответ 4

У вас бесконечный цикл. while (Part >= 0) при том, что Part инициализируется 1, а
потом ее можно очень долго делить на 10, всегда будет больше 0

UPD Part = Part / 10; Всегда будет больше 0, и из цикла while (Part >= 0) вы никогда
не выйдете.


Ответ 5

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

// вспомогательная функция: сумма цифр
static int SumOfDigits(int n)
{
    int result = 0;
    while (n > 0)
    {
        result += n % 10;
        n /= 10;
    }
    return result;
}

// главная функция
public static int F(int n)
{
    // выход из рекурсии для чисел меньше 10
    if (n < 10)
        return F1(n);

    int result = 0;

    // обрабатываем по одной цифре справа налево
    // для маски 10000 текущее число будет иметь форму xyz..t0000
    for (int mask = 1; n > 0; mask *= 10)
    {
        // выбираем число t0000
        int lastPart = n % (mask * 10);
        // делим его на цифру и степень
        result += FDigitTimesPowerOfTen(lastPart / mask, mask);

        // убираем обработанную цифру
        n -= lastPart;
        // компенсация: на каждом числе из убранной части
        // нужно добавить цифры остатка
        result += lastPart * SumOfDigits(n);
    }

    return result;
}

// вычисление функции для числа вида t00000
// в этом случае digit = t, mask = 10000 (степень десятки)
static int FDigitTimesPowerOfTen(int digit, int mask)
{
    if (digit == 0)
        return 0;
    // заменяем все старшие цифры на 0
    // при этом для компенсации добавляем 1000...0 раз убранные цифры
    // то есть F1(digit - 1)
    return FPowerOfTen(mask) * digit + F1(digit - 1) * mask;
}

// кэш для степеней десятки
static Dictionary FPowerOfTenCache = new Dictionary(100) { {
1, 1 } };
// вычисление функции для степеней десятки
static int FPowerOfTen(int n)
{
    int result;
    if (!FPowerOfTenCache.TryGetValue(n, out result))
    {
        // n-1 имеет на одну цифру меньше, спускаемся рекурсивно
        result = 1 + F(n - 1);
        FPowerOfTenCache[n] = result;
    }
    return result;
}

// функция для одноцифрового числа - сумма арифметической прогрессии
static int F1(int n)
{
    Debug.Assert(0 <= n && n < 10);
    return n * (n + 1) / 2;
}