Код на языке Go для решения задачи⁚
go
package main
import (
″fmt″
″sort″
)
func isRobberyPossible(n int, a []int) bool {
m ⁚ len(a)
if m 0 {
return false
}
// Сортируем массив номиналов купюр по возрастанию
sort.Ints(a)
// Проверяем, что номиналов достаточно для суммы n
if a[0]*2 > n || a[m-1]*2 < n {
return false
}
// Используем два указателя для перебора всех возможных пар купюр
left ⁚ 0
right ⁚ m ౼ 1
for left < right {
sum ⁚ a[left] a[right]
if sum n {
return true
} else if sum < n {
left
} else {
right—
}
}
return false
}
func main {
var n int
fmt.Print(″Введите сумму долларов, которую грабитель хочет украсть⁚ ″)
fmt.Scanln(nn)
var m int
fmt.Print(″Введите количество номиналов купюр⁚ ″)
fmt.Scanln(nm)
fmt.Println(″Введите номиналы купюр⁚″)
a ⁚ make([]int, m)
for i ⁚ 0; i < m; i {
fmt.Scan(na[i])
}
if isRobberyPossible(n, a) {
fmt.Println(″Грабитель может украсть″, n, ″долларов!″)
} else {
fmt.Println(″Грабителю не удалось заполучить″, n, ″долларов.″)
}
}
Объяснение кода⁚
1. Создаем функцию `isRobberyPossible`, которая проверяет, возможно ли провести ограбление суммы `n` с использованием купюр с номиналами `a`.
2. Внутри функции сортируем массив `a` в порядке возрастания, чтобы упростить дальнейший алгоритм.
3. Проверяем, что сумма всех номиналов в массиве достаточна для суммы `n`. Если наименьший номинал `a[0]` умноженный на 2 больше `n`, или наибольший номинал `a[m-1]` умноженный на 2 меньше `n`, то возвращаем `false`, так как невозможно получить `n` долларов.
4. Используем два указателя `left` и `right`, которые будут указывать на два разных номинала купюр.
5. Пока `left` меньше `right`, на каждой итерации считаем сумму `sum` двух купюр, на которые указывают указатели.
6. Если `sum` равно `n`٫ то возвращаем `true`٫ так как нашли пару купюр٫ которые в сумме дают `n` долларов.
7. Если `sum` меньше `n`٫ то сдвигаем левый указатель `left` вправо٫ чтобы увеличить сумму.
8. Если `sum` больше `n`, то сдвигаем правый указатель `right` влево, чтобы уменьшить сумму.
9. Если на всех итерациях не нашли пару купюр с суммой `n`, возвращаем `false`.
10. В функции `main` осуществляем ввод данных от пользователя⁚ суммы долларов `n`, количества номиналов `m` и номиналов купюр `a`.
11. Затем вызываем функцию `isRobberyPossible` с передачей в нее введенных данных и выводим соответствующий результат.