tạo thành một số sử dụng các số liên tiếp

Question

Tôi đã bối rối với một trong những câu hỏi trong phỏng vấn của Microsoft như sau:

Chức năng phải chấp nhận phạm vi (3 - 21) và nó phải in tất cả các số liên tiếp để tạo thành từng số như được nêu dưới đây:

 
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

bạn có thể giúp tôi tạo thành chuỗi này trong C# không?

Cảm ơn, Mahesh

Answer 1

Vì vậy, đây là một câu trả lời đơn giản/ngây thơ (trong C++, và không được kiểm tra, nhưng bạn sẽ có thể để dịch). Nó sử dụng thực tế là

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

mà bạn có thể nhìn thấy trước. Có rất nhiều tối ưu hóa dễ dàng có thể được thực hiện ở đây mà tôi đã bỏ qua cho rõ ràng.

---

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

Đây là một số mã giả để tìm tất cả các kết hợp nếu có tồn tại:

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 

Một cuộc gọi đến all_consecutive_numbers (21) sẽ in:

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

tôi thử nghiệm nó trong ruby ​​(mã here) và nó có vẻ hoạt động. Tôi chắc rằng ý tưởng cơ bản cũng có thể dễ dàng được triển khai trong C#.

Answer 3

Đây là một cái gì đó trong Groovy, bạn sẽ có thể hiểu những gì đang xảy ra. Nó không phải là mã hiệu quả nhất và không tạo ra các câu trả lời theo thứ tự bạn trích dẫn trong câu hỏi của bạn (dường như bạn đang thiếu một số câu hỏi) nhưng nó có thể cho bạn một sự khởi đầu.

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

Output cho f(3,21) là:

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 

Hope this helps. Nó phù hợp với nguyên lý làm điều đơn giản nhất có thể làm việc.

Answer 4

Tôi thích vấn đề này. Dưới đây là một slick và hơi bí ẩn O (n) giải pháp:

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

nếu chúng ta cắt một thành 2 chữ số, sau đó a = b + (b + 1) = 2 * b + (0 + 1)
nếu chúng ta cắt thành 3 chữ số, thì a = b + (b + 1) + (b + 2) = 3 * b + (0 + 1 + 2)
...
nếu chúng ta cắt thành chữ số n , sau đó a = b + (b + 1) + ... + (b + n) = n b + (0 + 1 + n-1)
kết quả cuối cùng là a = n b + n * (n-1)/2, a, b, n là tất cả ints.
nên O (N) Thuật toán là:

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