Задача: Есть последовательность чисел 3,5,7,9,11,...n до бесконечности. Требуется найти из данной последовательности такие числа A и B, что сумма всех чисел из этой последовательности от А до В включительно будет равна некоторому числу N. Между А и В должен быть хотя бы один член последовательности. (По условию все N - такие). Программа должна работать не более минуты.

Пример: Предположим наше число N равно 77, тогда числа A и B примут следующие значения:

A 5 7 9 11 13 15 B19 21 23 25 .. X2 Y2

A=3

B=17

A+5+7+...+B=77

Все началось с того, что на одном из сайтов для удаленной работы мне под руку попалась данная задачка в несколько ином оформлении. Так как я в основном программирую на Visual Basic и в принципе немного разбираюсь в математике, то она меня сильно заинтересовала.

Для начала я попытался решить ее посредством простейшего перебора, - это первое, что пришло мне в голову.

Для этого в среде Vb создал новый проект, и на форму (см. рисунок) набросил следующие элементы:

TextBox:                 Text1

TextBox:                 Text2

TextBox:                 Text3

TextBox:                 Text4

CommandButton:   Command1

В поле �NumberN� требуется ввести число N, и после нажатия на кнопку �Find A and B� в полях �Number A� и �Number B� появляются расчитанные числа A и B, а в поле �Count n� � количество числе между A и B.

Нетрудно заметить, что последовательность 3,5,7,9,11,... представляет собой арифметическую прогрессию с разностью равной 2 (5-3=2,�.).

Любой элемент математической прогрессии можно расчитать по следующей формуле:

A_n=A₁+d(n-1), где

A₁-первый член прогрессии, d � разность прогрессии, n  - номер взятого члена).

Сумма первых n членов арифметической прогрессии определяется по следующей формуле:

S_n=(A₁+A_n)*n/2

Option Explicit

Dim N As Double

Dim X As Double

Dim Y As Double

Dim Numfind As Boolean

Private Sub Command1_Click()

Text2.Text = " "

Text3.Text = " "

Text4.Text = " "

Algoritm1

End Sub

Public Function Algoritm1()

Dim i, j, Z, Sij

N = Text1.Text

Numfind = False

If (N Mod 2 = 0) Then

    Z = N - 1

Else

    Z = N - 2

End If

For i = 3 To Z Step 2 'это первый элемент - A1

    For j = i + 2 To Z Step 2 'а это второй An

        Sij = ((i + j) / 2) * (j - i + 2) / 2 'определяем сумму

           If (Sij = N) Then

            X = i

            Y = j

            Numfind = True

           Exit For

       End If

        If (Sij > N) Then Exit For

    Next j

If (Sij = N) Then Exit For

Next i

If (Numfind = True) Then

    Text2.Text = X

    Text3.Text = Y

    Text4.Text = (Y - X + 2) / 2

End If

End Function

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

Т.к. в задаче также уделяется внимание времени работы, то я решил проанализировать полученные результаты и найти более быстрый алгоритм решения данной задачи. Для анализа я решил найти числа A и B для нескольких N и проанализировать полученные данные. Вот что я получил (см. таблицу):

После двух дней размышлений я заметил, что число N во всех случаях делится на количество чисел между A и B (Count N)  без остатка (21/3=7, 32/4=8,.. 2523/3=841,�). Данное открытие позволяет намного упростить код алгоритма и задача решается мгновенно практически для любого числа. Алгоритм имеет следующий вид:

Option Explicit

Dim N As Double

Dim X As Double

Dim Y As Double

Dim Numfind As Boolean

Private Sub Command1_Click()

Text2.Text = " "

Text3.Text = " "

Text4.Text = " "

Algoritm2

End Sub

Public Function Algoritm2()

Dim i, j, Z, a

Dim A1 As Double

Dim SA1i As Double

Dim RightNum As Integer

Dim NumToStr As String

RightNum = Right(Text1.Text, 2)

N = Text1.Text

Numfind = False

If (RightNum Mod 2 = 0) Then

    a = 4 'если четное число N, то количество чисел в ряду также четное

Else

    a = 3

End If

For i = a To 1000000 Step 2 'i- количество элементов в ряду между A и B

If ((N / i) = (Int(N / i))) Then 'проверяем делимость без остатка

    A1 = (N + i - i ^ 2) / i

    SA1i = i * (i + A1 - 1)

    If (SA1i = N) Then

        X = A1

        Y = A1 + i * 2 - 2

        Numfind = True

    End If

 End If

 If (Numfind = True) Then Exit For

Next i      

If (Numfind = True) Then

    Text2.Text = X

    Text3.Text = Y

    Text4.Text = i

End If

End Function

Программа в конечном исполнении имеет следующий вид (рис):

Опция �1 Алоритм� соответствует первому алгоритму (с полным перебором), а �2 Алоритм� � 2 алгоритму (более быстрому).

Приму любые замечания и предложения по работе программы.

Данную программу �NumberSum� можно скачать отсюда:

http://artmetals.narod.ru/programes/NumberSum.exe