Я был озадачен одним из вопроса в интервью 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#?
Спасибо, Mahesh
Итак, вот простой / наивный ответ (на 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 << " + ";
}
}
}
}
}
Мне нравится эта задача. Вот изящное и немного загадочное решение 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);
}
}
}
}
Вот кое-что в 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
Надеюсь, это поможет. Это как бы соответствует принципу делать простейшие вещи, которые только могут сработать.
Вот псевдокод для поиска всех комбинаций, если таковые существуют:
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#.
если мы разбиваем a на 2 разряда, то a = b + (b+1) = 2*b + (0+1)
если разделить a на 3 цифры, то a = b + (b+1) + (b+2) = 3*b + (0+1+2)
...
если разделить a на n цифр, то a = b + (b+1) +...+ (b+n) = nb + (0+1+n-1)
последний результат - a = nb + 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++;
}
}