Логические задачи.

[burning_LEGION]

Две мухи между собой соревнуются. Они бегут от пола к потолку, а затем обратно. Первая муха бежит и вверх и вниз с одинаковой скоростью. Вторая муха бежит вниз вдвое быстрее, чем первая. А вверх она бежит вдвое медленнее. Какая из мух победит?

равномерная муха вин, а где тут логика кстати?)

 

[sto2299]

а где тут логика кстати?

Почему нормальная логическая задача. На первый взгляд кажется что мухи придут одинаково.

 

[burning_LEGION]

про мудрецов была логическая, про немца с рыбкой логическая, а эта просто с подвохом, ответ однозначный и легко вычисляемый, а то что есть очевидный неправильный вариант это какая-то фигня, как каптча при отправке сообщения =)

 

[sto2299]

burning_LEGION

Предложи свою логическую задачу.

 

[burning_LEGION]

так я и знал =)

есть массив int[100] целых чисел от 1 до 100 (без дублей), перемешиваем, удаляем любое число, надо найти это число, простой перебор это 100 по 100 = 10000 операций, надо побыстрее, вопрос как?

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

 

[sto2299]

Не совсем тебя понял

простой перебор это 100 по 100

 

[burning_LEGION]

это уже пояснение, если начнешь перебирать все варианты в лоб будет 10к сравнений, нужно оптимальнее

 

[sto2299]

Насколько я понял удалённое число мы ищем следующим образом.
Берём первое число в массиве и сравниваем на равенство начиная с единицы и заканчивая 100. Если будет равенство то это есть первое определённое число в массиве, потом таким образом определяем второе и т.д. После всего смотрим какого числа нет - это и будет наше удалённое число.

Например рассмотрим самый плохой вариант.

Удалённое число 1, а числа в массиве были перемешаны по убывающей от 100 до 1 - которую мы удалили.

Тогда для определения 100 на понадобится 100 сравнений, для определения 99 - 99, для 98 -98. В общем 10000 сравнений никак не получается при самом плохом раскладе.

 

[burning_LEGION]

да, я округлил чуть-чуть, но суть дела это не меняет

 

[sto2299]

да, я округлил чуть-чуть

это ты не чуть чуть округлил, а округлил на много если не ошибаюсь в самом плохом варианте будет 5000 сравниваний, а не 10000

 

[burning_LEGION]

это ты не чуть чуть округлил, а округлил на много если не ошибаюсь в самом плохом варианте будет 5000 сравниваний, а не 10000

ну не важно =) пусть хоть 3к главное что это все равно на порядок больше чем нужно

 

[sto2299]

Завтра продолжу думать. Сейчас что то ничего дельного на ум не приходит........

 

[avbua]

есть массив int[100] целых чисел от 1 до 100 (без дублей), перемешиваем, удаляем любое число, надо найти это число, простой перебор это 100 по 100 = 10000 операций, надо побыстрее, вопрос как?

Создаём массив int1[100] забитый нулями, делаем один проход и в int1 помечаем единицами существующие числа, вторым проходом в int1 ищем 0

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

Как по мне, то это уже не оптимизируется, обычный перебор. Можно отсортировать и выкинуть числа более 51, но выигрыш сомнительный.

 

[burning_LEGION]

Сумма всех чисел от 1 до 100 = 5050
если из 5050 вычесть сумму перемешанных цифр, это и даст то число, которое было исключено из массива.

верно

а ответ на 2ю задачу я не знаю, тот кто загадывал ее мне ответ не сказал, сказал только: "спасибо, мы вам перезвоним" =)

 

[sto2299]

Сумма всех чисел от 1 до 100 = 5050
если из 5050 вычесть сумму перемешанных цифр, это и даст то число, которое было исключено из массива.

Я вчера немного другое решение придумал.

Сумма двух чисел это одно действие, необходимо просуммировать все числа. При убирании какого нибудь числа получатся разные суммы, эти суммы можно заранее узнать. Получаем суммирование чисел уже с удалённым числом составит 98 действий, а потом надо сравнить на равенство со всеми предполагаемыми числами - чисел будет 100, то есть это ещё 100 действий и того получаем 198 действий.

Но решение предложенное JAZZ ещё оптимальней - если не считать сумму 5050 за действие, то в таком случае в итоге получим 99 действий.

Вторую задачу буду сейчас думать.



Оптимальное решение второй задачи:

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

пока не нашёл.

Предложу вот какое:

52 можно получить следующим образом:

51+1
50+2
49+3
....
26+26
далее числа будут повторяться.
Поэтому нам надо сравнивать числа от 1 до 51, это в наихудшем варианте 5100 сравнений.

Пока получается 5100 действий.
Может кто предложит меньше.......

даже 5200 действий так как надо искать два числа 26.

 

[avbua]

есть массив int[100] целых чисел от 1 до 100 (могут быть дубли), перемешиваем, задача найти 2 числа, сумма которых составит 52, ну и как обычно надо пооптимальнее

1. сортируем по возрастанию
2. слева становимся на нулевой элемент (Left=0), справа становимся на последний элемент, который меньше 52 (Right=...).
3. Если их сумма равна 52 или Left==Right, то выход
4. Если их сумма <52, то Left++ и goto 3.
5. Если их сумма >52, то Right-- и goto 3.

PS: C Днём Космонавтики всех!

 

[burning_LEGION]

1. сортируем по возрастанию
2. слева становимся на нулевой элемент (Left=0), справа становимся на последний элемент, который меньше 52 (Right=...).
3. Если их сумма равна 52 или Left==Right, то выход
4. Если их сумма <52, то Left++ и goto 3.
5. Если их сумма >52, то Right-- и goto 3.

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

 

[avbua]

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

но всё равно быстрее предыдущих ответов

Останется найти два одинаковых элемента этих массивов

И нас отбросило на начало задачи

1. сортируем по возрастанию
2. слева становимся на нулевой элемент (Left=0), справа становимся на последний элемент, который меньше 52 (Right=...).
3. Если их сумма равна 52 или Left==Right, то выход
4. Если их сумма <52, то Left++ и goto 3.
5. Если их сумма >52, то Right-- и goto 3.

PS: C Днём Космонавтики всех!

Второй вариант, ещё проще.
1. Создаём масив My[100], забиваем нулями
2. Первый проход, инкрементируем в этом массиве существующие элементы. My[source]++
3. четверть прохода (1-25), ищем пару с ненулевыми My и My[52-i]
4. Если не нашли, проверяем количество чисел 26



Простенькая задачка. Есть две целые переменные A и B. Как поменять местами их значения, не прибегая к помощи третьей переменной?

 

[crghome]

Простенькая задачка. Есть две целые переменные A и B. Как поменять местами их значения, не прибегая к помощи третьей переменной

A+=B;
B=A-B;
A-=B;

OR ON Delphi

A:=A+B;
B:=A-B;
A:=A-B;

 

[burning_LEGION]

Простенькая задачка. Есть две целые переменные A и B. Как поменять местами их значения, не прибегая к помощи третьей переменной?

сложением по модулю 2

A+=B;
B=A-B;
A-=B;

A=3 B=1

A=3+1
B=1+4
A=4-5

A=-1 B=5
so close.....