tworzą szereg wykorzystujący kolejne numery

Question

ja zaskoczony z jednym z pytanie w programie Microsoft wywiadzie, który jest podany poniżej:

Funkcja powinna przyjmować szereg (3 - 21) i powinien wydrukować wszystkie kolejne kombinacje liczb tworząc każdy numer, jak podano poniżej:

 
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

mógłbyś mi pomóc w tworzeniu tej sekwencji w C#?

Dzięki Mahesh

Answer 1

Więc tutaj jest prosta odpowiedź naiwny/(w C++, a nie testowane, ale powinien być w stanie przetłumaczyć). Wykorzystuje fakt, że

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

które masz prawdopodobnie widział. Istnieje wiele łatwych optymalizacji, które można tutaj pominąć dla jasności.

---

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

to niektóre pseudo kod, aby znaleźć wszystkie kombinacje jeśli istnieje:

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 

Wywołanie all_consecutive_numbers (21) by wydrukować:

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

Testowałem w rubinie (kod here) i wydaje się działać. Jestem pewien, że podstawowy pomysł może być łatwo zaimplementowany również w języku C#.

Answer 3

Oto coś w Groovy, powinieneś być w stanie zrozumieć, co się dzieje. Nie jest to najskuteczniejszy kod i nie tworzy odpowiedzi w kolejności, którą cytujesz w swoim pytaniu (wydaje się, że brakuje ci niektórych), ale może to dać ci początek.

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]}" 
    } 
    } 
} 

Wyjście f(3,21) jest:

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 

Nadzieja to pomaga. Jest to zgodne z założeniem robienia najprostszej rzeczy, która mogłaby działać.

Answer 4

Podoba mi się ten problem. Tutaj jest gładkie i lekko tajemnicza O (n) roztworu:

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

jeśli plaster postaci 2 cyfra, to: a = b + (b + 1) = 2 * b + (0 + 1)
jeśli podzielimy na 3 cyfry, wówczas a = b + (b + 1) + (b + 2) = 3 * b + (0 + 1 + 2)
... jeśli podzielimy na n cyfrę , a następnie a = b + (b + 1) + ... + (b + n) = n b + (0 + 1 + n-1)
Ostatni wynik to a = n b + n * (n-1)/2, a, b, n są wszystkie ints.
więc O (N) Algorytm jest:

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++; 
    } 
}