Вот такая задачка (сам придумал) ;-)

← →
Igorek © (2002-06-02 08:06) [0]

Дано:
Числа N и K.
Масивы A[N] и B[N], случайным образом заполненные значениями 0 и 1.
Функция function f(i: Integer): Boolean, про которую известно, что она:
1) возвращает true если масивы А и В одинаковы и false - если нет.
2) если аргумент в дипазоне от 1 до К, тогда:
в зависимости от аргумента инвертирует значения определенных элементов масива А (каких именно - однозначно зависит от аргумента)
если нет, то ничего не делает

Требуется:
Добиться от функции f возвращения true минимальным числом ее вызовов (если это возможно).
Прямого доступа к массивам А и В нет.
С фукцией f можно предварительно потренироваться.

Еще сам не решил ;-)

← →
Igorek © (2002-06-03 15:12) [1]

Эй где вы, любители крепких орешков? MBo, MrSimm?
Мне уж самому эта задачка все больше начинает нравиться :-)

← →
Виктор Щербаков © (2002-06-03 15:31) [2]

ИМХО, очень мало известно о функции f. Вернее о зависимости номеров инвертируемых элементов массива от аргумента.

← →
VictorT © (2002-06-03 15:37) [3]

Я так понял, это получается задачка про "чёрный ящик", которым и является функция f. Её не всегда можно однозначно решить.

← →
SPeller © (2002-06-03 15:38) [4]

for i:=n downto 1 do if a[i]<>b[i] then f(i);

← →
SPeller © (2002-06-03 15:39) [5]

Здесь имеется ввиду что ф-я f инвертирует эл-ты от 1 до i

← →
SPeller © (2002-06-03 15:40) [6]

Хотя можно инвертировать только эл-т с номером i

← →
VictorT © (2002-06-03 15:51) [7]

> SPeller © (03.06.02 15:38)

А в условии сказано, что прямого доступа к массивам нет.

← →
SPeller © (2002-06-03 15:59) [8]

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

← →
Igorek © (2002-06-03 16:34) [9]

Я думаю известно достаточно, если вчитаться.
1) Инвертировать напр. A[1] - значит A[1] = 1 - A[1]
2) Функция f инвертирует значения определенных элементов масива А (каких именно - однозначно зависит от аргумента

Я бы даже ужесточил условие: никаких тренировок с f, все вызовы считаются.

Кроме того перебрать варианты - это не решить задачу.
Надо определить кратчайшую последовательность вызовов f и параметр в каждом случае.

Уточню, во избежание недоразумений.
Известны числа N и K, масивы A[N] и B[N].

И всё равно задание твоё непонятное. Допустим N>K тогда если эл-ты массива выше К разные, то никаким макаром мы их не уравняем. А посчитать параметр и вычислить сколько раз - это ты сам будешь считать в зависимости от содержания массивов и их размерности. Здесь всё относительно.

Да и вообще, зачем мозги парить? На практике всё-равно такое не встречается.

2SPeller
Очень даже полезная практически задачка.

Вот такая задачка (сам придумал) ;-) Найти похожие ветки