сформируйте число, используя последовательные числа

Question

Я был озадачен одним из вопросов в интервью Microsoft, как указано ниже:

Функция должна принимать диапазон (3 - 21) и печатать все последовательные комбинации чисел для формирования каждого числа, как указано ниже:

3  = 1+2
5  = 2+3
6  = 1+2+3
7  = 3+4
9  = 4+5
10 = 1+2+3+4
11 = 5+6
12 = 3+4+5
13 = 6+7
14 = 2+3+4+5
15 = 1+2+3+4+5
17 = 8+9
18 = 5+6+7
19 = 9+10
20 = 2+3+4+5+6
21 = 10+11
21 = 1+2+3+4+5+6

Не могли бы вы помочь мне в формировании этой последовательности в C #?

Спасибо, Махеш

Answer 1

Итак, вот простой / наивный ответ (на C ++, не проверенный; но вы должны быть в состоянии перевести). Он использует тот факт, что

1 + 2 + ... + n = n (n + 1) / 2,

что вы, наверное, видели раньше. Здесь можно сделать много простых оптимизаций, которые я пропустил для ясности.

---

void WriteAsSums (int n)
{
  for (int i = 0; i < n; i++)
  {
    for (int j = i; j < n; j++)
    {
      if (n = (j * (j+1) - i * (i+1))/2) // then n = (i+1) + (i+2) + ... + (j-1) + j
      {
        std::cout << n << " = ";
        for (int k = i + 1; k <= j; k++)
        {
          std::cout << k;
          if (k != j) // this is not the interesting bit
            std::cout << std::endl;
          else
            std::cout << " + ";
        }
      }
    }
  }
}

Answer 2

Это некоторый псевдокод для поиска всех комбинаций, если таковые существуют:

function consecutive_numbers(n, m)
    list = [] // empty list
    list.push_back(m)
    while m != n
        if m > n
            first = list.remove_first
            m -= first
        else
            last = list.last_element
            if last <= 1
                return [] 
            end
            list.push_back(last - 1) 
            m += last - 1
        end
    end
    return list
end

function all_consecutive_numbers(n)
    m = n / 2 + 1
    a = consecutive_numbers(n, m)
    while a != []
        print_combination(n, a)
        m = a.first - 1
        a = consecutive_numbers(n, m)
    end
end

function print_combination(n, a)
    print(n + " = ")
    print(a.remove_first)
    foreach element in a
        print(" + " + element)
    end
    print("\n")
end

Вызов all_consecutive_numbers (21) выдает:

21 = 11 + 10
21 = 8 + 7 + 6
21 = 6 + 5 + 4 + 3 + 2 + 1

Я проверил это в ruby ​​(код здесь ), и похоже, что оно работает Я уверен, что основная идея может быть легко реализована и в C #.

Answer 3

если мы нарежем a на 2 цифры, то a = b + (b + 1) = 2 * b + (0 + 1)
если мы нарежем на 3 цифры, то a = b + (b + 1) + (b + 2) = 3 * b + (0 + 1 + 2)
...
если мы нарежем a на цифру n, то a = b + (b + 1) + ... + (b + n) = n b + (0 + 1 + n-1)
последний результат равен a = n b + n * (n-1) / 2, a, b, n - целые числа.
поэтому алгоритм O (N):

void seq_sum(int a)
{
// start from 2 digits
   int n=2;
   while(1)
   {
      int value = a-n*(n-1)/2;
      if(value < 0)
         break;
// meet the quotation we deduct
      if( value%n == 0 )
      {
           int b=value/n;
// omit the print stage
           print("......");
      }
      n++;
   }
}

Answer 4

Мне нравится эта проблема. Вот гладкое и немного загадочное решение O (n):

void DisplaySum (int n, int a, int b)
{
  std::cout << n << " = ";
  for (int i = a; i < b; i++) std::cout << i << " + ";
  std::cout << b;
}

void WriteAsSums (int n)
{
  N = 2*n;

  for (int i = 1; i < N; i++)
  {
    if (~(N%i))
    {
      int j = N/i;
      if (j+i%2)
      {
        int a = (j+i-1)/2;
        int b = (j-i+1)/2;
        if (a>0 & a<b) // exclude trivial & negative solutions
          DisplaySum(n,a,b);
      }
    }
  }
}

Answer 5

Вот что-то в Groovy, вы должны быть в состоянии понять, что происходит. Это не самый эффективный код, и он не создает ответы в том порядке, в котором вы цитируете свой вопрос (хотя, похоже, вам не хватает некоторых), но это может дать вам начало.

def f(a,b) {

  for (i in a..b) {

    for (j in 1..i/2) {

      def (sum, str, k) = [ 0, "", j ]

      while (sum < i) {
        sum += k
        str += "+$k"
        k++
      }

      if (sum == i) println "$i=${str[1..-1]}"
     }
  }
}

Выход для f(3,21):

3=1+2
5=2+3
6=1+2+3
7=3+4
9=2+3+4
9=4+5
10=1+2+3+4
11=5+6
12=3+4+5
13=6+7
14=2+3+4+5
15=1+2+3+4+5
15=4+5+6
15=7+8
17=8+9
18=3+4+5+6
18=5+6+7
19=9+10
20=2+3+4+5+6
21=1+2+3+4+5+6
21=6+7+8
21=10+11

Надеюсь, это поможет. Это как бы соответствует принципу простейшего действия, которое могло бы сработать.