@Bobiys

Как работает программа?

Что происходит в коде этой программы, по какому принципу она выбирает числа из массива?

Задача : Даны N целых чисел X1, X2, ..., XN. Расставить между ними знаки "+" и "-" так, чтобы значение получившегося выражения было равно заданному целому S.

Входные данные
В первой строке находятся числа N и S. В следующей строке - N чисел через пробел. 2 <= N <= 24, 0 <= Xi <= 50 000 000, -1 000 000 000 <= S <= 1 000 000 000.

Выходные данные
Если получить требуемый результат невозможно, вывести "No solution", если можно, то вывести равенство. Если решение не единственное, вывести любое.

Решение, которое нашел :

spoiler
Var n , i , j : longint;
    a : array[1..25] of int64;
    res , s : int64;
    found : boolean;
 
Function getBit(i , j : longint) : longint;
Begin
    if (i and (1 shl j)) <> 0 then
        getBit := 1
    else
        getBit := 0;    
End;
 
Begin
    Read(n , s);
    for i := 1 to n do
        Read(a[i]);
    for i := 0 to (1 shl (n - 1)) - 1 do begin
        res := a[1];
        for j := 0 to n - 2 do 
            if getBit(i , j) = 0 then
                res := res + a[2 + j]
            else
                res := res - a[2 + j];  
        if res = s then begin
            Write(a[1]);
            for j := 0 to n - 2 do
                if getBit(i , j) = 0 then
                    Write('+' , a[2 + j])
                else
                    Write('-' , a[2 + j]);
            found := true;
            WriteLn('=' , s);
            break;  
        end;
    end;    
    if not found then
        WriteLn('No solution');
End.
  • Вопрос задан
  • 144 просмотра
Решения вопроса 1
Bavashi
@Bavashi
Программа работает принципу перебора всех возможных значений сложения и вычитания для заданных цифр, то есть у вас, например, на входе 5 цифр. Знаков сложения и вычитания у них может быть 4. Так как значения может быть два, плюс и минус, то число комбинаций равно 2^4=16. Посмотрим где, это описывается в коде:
for i := 0 to (1 shl (n - 1)) - 1 do begin
Здесь важно понимать как работает 1 shl (n - 1): это битовый сдвиг влево числа 1 на (n-1) бит. Эта операция эквивалентна операции возведения числа 2 в степень (n-1). Например:
  • 1 shl 3 = 1000 (в двоичной системе счисления) = 8 (в десятичной системе счисления), то есть это эквивалентно записи 2^3=8.
  • 1 shl 4 = 10000 (в двоичной системе счисления) = 16 (в десятичной системе счисления), то есть это эквивалентно записи 2^4=16.

Далее, важно понимать как работает побитовая операция в этой строке:
if (i and (1 shl j)) <> 0
1 shl j мы разобрали, нужно разобрать and, который в данном случае это побитовая операция умножения. Например:
  • (1 and 2) = (01 and 10) (в двоичной системе счисления, перемножаем обычным столбиком) = 00 = 0 (в десятичной системе счисления)
  • (2 and 3) = (10 and 11) (в двоичной системе счисления, перемножаем обычным столбиком) = 10 = 2 (в десятичной системе счисления)

Это нужно для того, чтобы можно было чередовать значения плюсов и минусов. Другими словами, функция getBit будет в цикле давать нам значения для перебора плюсов и минусов.
Далее смысл такой, что берем число цифр на входе, вычитаем из него 1 и получаем кол-во знаков, которые могут быть. Далее считаем кол-во возможных комбинаций этих знаков через цикл и пробегаемся по всем значениям плюсов и минусов сравнивая с S.

Попробую описать это через комментарии в коде

// В этом блоке просто объявлеям переменные
Var n , i , j : longint;
    a : array[1..25] of int64;
    res , s : int64;
    found : boolean;

// Та самая функция, которая будет нам чередовать значения.
// Например, если у нас 3 числа, то знаков 2, соответственно
// всех возможных комбинаций 2^2=4. Функция getBit, при итерации из цикла ниже,
// будет возращать нам такие последовательность нулей и единиц:
// 00
// 01
// 10
// 11
// Что будет являться перебором всех комбинаций. При этом надо учитывать, что
// 1 - это все что больше нуля. Поэтому в строке есть сравнение с нулем.
Function getBit(i , j : longint) : longint;
Begin
    if (i and (1 shl j)) <> 0 then
        getBit := 1
    else
        getBit := 0;    
End;

// Начинаем главный блок программы
Begin
    Read(n , s); // Считали ввод от пользователя
    for i := 1 to n do
        Read(a[i]); // Занесли все в массив через цикл
    for i := 0 to (1 shl (n - 1)) - 1 do begin // Объявляем главный цикл. Значение (1 shl (n - 1)) эквивалентно возведению в степень.
        res := a[1]; // В переменную res записали первое значние массива
        for j := 0 to n - 2 do // Делаем вложенный цикл. Вычитаем 2, потому что знаков (+/-) меньше цифр на 1 и потому что значения в массиве начинаем с нуля.
            if getBit(i , j) = 0 then // Вызвали функцию для чередования
                res := res + a[2 + j] // Если getBit вернул 0, то к первому значению массива плюсуем второе и т.д
            else
                res := res - a[2 + j]; // Если getBit вернул 1, то к первому значению массива минусуем второе и т.д 
        if res = s then begin // Проверям на данной цепочке минусов и плюсов получили ли заданное юзером S? Если нет, то вышли на цикл выше и увеличили i.
            Write(a[1]); // Если получили равенство с S, то записываем первое значение массива и делаем тоже самое, что и в цикле с j, то есть повторяем туже самую цепочку для i, но для вывода.
            for j := 0 to n - 2 do
                if getBit(i , j) = 0 then
                    Write('+' , a[2 + j])
                else
                    Write('-' , a[2 + j]);
            found := true; // Отметили, что решение нашли
            WriteLn('=' , s);
            break;  // Вышли из цикла
        end;
    end;    
    if not found then // Если не нашлось такой цепочки плюсов и минусов, при которой получаем S, то решения нет.
        WriteLn('No solution');
End.

Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
03 июн. 2020, в 02:34
2000 руб./за проект
02 июн. 2020, в 23:49
1000 руб./в час
02 июн. 2020, в 23:26
5000 руб./за проект