Без какой величины можно решить эту задачу

1. Текстовые задачи и их решение арифметическим способом

Решить задачу арифметическим способом — это значит найти ответ на требование задачи посредством выполнения арифметических действий над данными в задаче числами.

Обрати внимание!

В учебнике встречаются задачи:

• на движение;
• на применение действий сложения и вычитания натуральных чисел;
• приводящие к делению, умножению натуральных чисел;
• на отработку отношений «на какое-то число больше», «на какое-то число меньше», «в какое-то число раз больше», «в какое-то число раз меньше», «всего»;
• на части;
• на совместную работу;
• на предполагаемое и фактически выполненное;
• с использованием рисунков, диаграмм.

Выполняя решение задачи, нужно провести анализ текста задачи и

последовательно ответить на вопросы по условию задачи.

1. Какие величины надо знать, чтобы ответить на вопрос задачи?
2. Какая из величин известна, а какая нет?

3. Что нужно знать, чтобы найти эту величину?

4. Как это узнать, исходя из условия задачи?

2. Размещения

Размещением из \(n\) элементов по \(m\) элементов ( m ≤ n ) называется упорядоченная выборка элементов \(m\) из данного множества элементов \(n\).

Количество размещений из \(n\) элементов по \(m\) элементов обозначается A n m (читается как «размещение из \(n\) элементов по \(m\) элементов»).

Число \(m\) показывает количество элементов размещения (сколько элементов выбирается).
Число \(n\) показывает количество элементов данного множества.
Размещения вычисляются по формуле A n m = n ! ( n − m ) ! .

1. Сколько двузначных чисел можно составить из цифр \(2; 3; 4; 5; 6\) (если цифры не должны повторяться)?

Решение:
выбираются \(2\) элемента из множества \(5\) элементов.

В данном случае \(n = 5\) (т. к. дано множество с \(5\) цифрами), а \(m = 2\) (т. к. нужно выбрать \(2\) цифры для числа).

Вычисляем A 5 2 .
По формуле: A 5 2 = 5 ! 5 − 2 ! = 5 ! 3 ! = 5 ⋅ 4 ⋅ 3 ! 3 ! = 5 ⋅ 4 ⋅ 3 ! 3 ! = 20 .
Ответ: из данных цифр можно составить \(20\) двузначных чисел с различными цифрами.
2. Даны элементы \(3\) разных цветов: зелёного, синего и красного.

Сколькими различными способами можно выбрать \(2\) из них, если порядок важен?
Решение:
эту задачу можно решить двумя способами: полным перебором или подставив величины в формулу.

1) 2) 3)

4) 5) 6)

Как видно на картинке, два элемента из всех данных можно выбрать \(6\) различными способами.

Подставив величины в формулу (\(n = 3\) и \(m= 2\)), получаем такой же результат: A 3 2 = 3 ! ( 3 − 2 ) ! = 3 ! 1 ! = 1 ⋅ 2 ⋅ 3 1 = 6 1 = 6 .

Динамическое программирование

Рассмотрим следующую задачу. В обороте находятся банкноты k различных номиналов: a₁, a₂, . a_k рублей. Банкомат должен выдать сумму в N рублей при помощи минимального количества банкнот или сообщить, что запрашиваемую сумму выдать нельзя. Будем считать, что запасы банкнот каждого номинала неограничены.

Рассмотрим такой алгоритм: будем выдавать банкноты наибольшего номинала, пока это возможно, затем переходим к следующему номиналу. Например, если имеются банкноты в 10, 50, 100, 500, 1000 рублей, то при N = 740 рублей такой алгоритм выдаст банкноты в 500, 100, 100, 10, 10, 10, 10 рублей. Подобные алгоритмы называют «жадными», поскольку каждый раз при принятии решения выбирается тот вариант, который кажется наилучшим в данной ситуации (чтобы использовать наименьшее число банкнот каждый раз выбирается наибольшая из возможных банкнот).

Но для решения данной задачи в общем случае жадный алгоритм оказывается неприменимым. Например, если есть банкноты номиналом в 10, 60 и 100 рублей, то при N = 120 жадный алгоритм выдаст три банкноты: 100 + 10 + 10, хотя есть способ, использующий две банкноты: 60 + 60. А если номиналов банкнот только два: 60 и 100 рублей, то жадный алгоритм вообще не сможет найти решения.

Но эту задачу можно решить при помощи метода динамического программирования. Пусть F(n) — минимальное количество банкнот, которым можно заплатить сумму в n рублей. Очевидно, что F(0) = 0, F(a₁) = F(a₂) =. = F(a_k) = 1. Если некоторую сумму n невозможно выдать, будем считать, что F(n) = (бесконечность).

Выведем рекуррентную формулу для F(n), считая, что значения F(0), F(1), . F(n — 1) уже вычислены. Как можно выдать сумму n? Мы можем выдать сумму n — a₁, а потом добавить одну банкноту номиналом a₁. Тогда нам понадобится F(n — a₁) + 1 банкнота. Можем выдать сумму n — a₂ и добавить одну банкноту номиналом a₂, для такого способа понадобится F(n — a₂) + 1 банкнота и т. д. Из всевозможных способов выберем наилучший, то есть:

F(n) = min(F(n — a₁), F(n — a₂). F(n — a_k)) + 1.

Теперь заведем массив F[n+1], который будем последовательно заполнять значениями выписанного рекуррентного соотношения. Будем предполагать, что количество номиналов банкнот хранится в переменной int k, а сами номиналы хранятся в массиве int a[k].

const int INF=1000000000; // Значение константы >бесконечность> 
int F[n+1]; 
F[0]=0; 
int m, i; 
for(m=1; m  < // m - сумма, которую нужно выдать 
F[m]=INF; // помечаем, что сумму m выдать нельзя 
for(i=0; i  < 
if(m>=a[i] && F[m-a[i]]+1 F[m] = F[m-a[i]]+1; // изменяем значение F[m], если нашли 
> // лучший способ выдать сумму m 
>

После окончания этого алгоритма в элементе F[n] будет храниться минимальное количество банкнот, необходимых, чтобы выдать сумму n. Как теперь вывести представление суммы n при помощи F(n) банкнот? Опять рассмотрим все номиналы банкнот и значения n — a₁, n — a₂, . n — a_k. Если для какого-то i окажется, что F(n — a_i) = F(n) — 1, значит, мы можем выдать банкноту в a_i рублей и после этого свести задачу к выдаче суммы n — a_i, и так будем продолжать этот процесс, пока величина выдаваемой суммы не станет равна 0:

if (F[n]==INF) 
coutelse 
while(n>0) 
for(i=0;i if (F[n-a[i]]==F[n]-1) 
 cout n-=a[i]; 
break; 
>

Вопросы-головоломки на собеседованиях с ответами. Часть 2

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

Work.ua подготовил еще 5 головоломок, которые могут встретиться на вашем пути.

Бильярдные шары

Этот вопрос чаще всего задают IT-специалистам, чтобы проверить способность логически мыслить.

Вопрос: Есть 8 бильярдных шаров. Один из них немного тяжелее других. За какое минимальное количество взвешиваний на рычажных весах без гирь можно найти этот шар?

Ответ: 2 взвешивания. Нужно разделить все шары на три части: по 3 шара в двух частях, и 2 шара в третьей части. Сначала взвешиваете первые две части по 3 шара. Если одна из частей оказалась тяжелее, то взвешиваем между собой любые 2 шара из нее. Или один из них будет искомым шаром, или не взвешенный, если они оказались равны. В случае равного веса частей при первом взвешивании, более тяжелый шар окажется в третьей части из двух шаров.

Дом

Вопрос: Нарисуйте дом.

Ответ: Казалось бы, что может быть проще. Рисуем квадрат, пару прямоугольников и треугольник наверху. А вот и нет. Этот тест рассчитан для должностей, которые требуют от сотрудника нестандартных решений и индивидуального подхода к каждой задаче (дизайнеров, менеджеров по рекламе). Во-первых, нужно проявить креативность, а не рисовать шаблонный дом. Во-вторых, нужно сперва уточнить для кого этот дом: кто в нем будет жить, и сколько будет этих жильцов. Не стоит приступать к работе, не узнав всех нюансов.

Вас могут попросить нарисовать не только дом, а все что угодно. Но всегда нужно узнавать все подробности, чтобы итоговый результат был правильным. А сам процесс будет значить намного больше, чем этот итоговый результат.

Слон

Вопрос: Как узнать вес слона без весов?

Ответ: Вариантов может быть очень много, вы ограничены лишь своей находчивостью и фантазией. Например, слона можно поставить на баржу и отметить ее осадку. Затем убрать слона и ставить на баржу предметы, вес которых вам известен — пятилитровые бутылки с водой, допустим. А когда осадка баржи будет такого же уровня как и со слоном, умножаем количество предметов на их вес. Тут главное — ваша изобретательность.

Драже M&M’s

Вопрос: Почему глазурь на известных драже M&M’s идеально гладкая? Как их делают, они что летают в воздухе?

Ответ: Еще один вопрос, правильный ответ на который не настолько важен, как варианты, предложенные кандидатом. Как бы вы решили эту задачу, если бы внезапно попали на производство? Держали бы драже на воздушном потоке? Приклеивали бы на нитку, где расположен логотип? На самом деле их опрыскивают глазурью во вращающемся барабане. Таким образом их поверхность остается гладкой, а глазурь наносится равномерно. Но ваш индивидуальный подход к решению этой задачи будет значить намного больше.

Русская рулетка

Решение этой задачи зависит от специфики вашей профессии. Ответ можно найти как с помощью точных вычислений, так и просто используя логику.

Вопрос: Есть шестизарядный револьвер. В нем 2 пули, обе расположены рядом друг с другом. Ваш оппонент раскручивает барабан, приставляет дуло к виску и нажимает на курок. Выстрела не произошло. Как поступите вы: сразу нажмете на курок или сперва снова раскрутите барабан?

Ответ: Правильный ответ один — сразу нажать на курок. Если произвести точные вычисления, то вероятность остаться в живых в этом случае составляет 75%, а если сперва раскрутить барабан — снижается до 66,7%. Так как пули расположены рядом друг с другом, можно логически определить, что лучше жать на курок сразу.

• Facebook share link
• Threads share link

139 комментариев

Кирилл Ерыганов 21.02.2013, 14:37

Спасибо, позабавили.
«Бильярдные шары»
Нам надо найти шар или группу шаров? Если шар — то 3 взвешивания (по 4, — по 2 из той группы, что тяжелее, — по 1 из той пары, что тяжелее). Приведенное в статье решение позволяет найти только ГРУППУ из 2 шаров.
«Русская рулетка»
Вероятность застрелиться из 6-зарядного револьвера с 2 патронами в барабане равна ровно 1/3 (2/6), независимо от расположения патронов, то есть шанс выжить — 2/3. Для обоих игроков. Независимо от того, раскручен барабан или нет. Оптимальное решение — выйти из игры. Вероятность выжить будет 100%.

Кирилл Ерыганов 21.02.2013, 15:38

Если при нераскрученном барабане не учитывать 1 пустую камеру, выпавшую первому игроку, то вероятность выстрела не уменьшится, а увеличится до 2/5 = 0,4, то есть шанс выжить упадет с 0,66 до 0,6.

Богдан Федис 21.02.2013, 15:47

Із більярдними кулями все вірно — потрібно тільки 2 зважування (сам зразу думав що 3).

А із рулеткою в умові сказано що патрони розміщені у барабані рядом(!). При такій умові, якщо перший гравець вижив, значить шанси вижити другого гравця — 3/4 — 3 слота без патронів (1 вже прокручений при першій спробі) і 1 із потроном = 75%.

Ну а якщо б перший застрелився то шанс другого був би 1/2 — фіфті/фіфті ))) це якщо не розкручувати, якщо ж прокрутити барабан 5/6 — 83%

Кирилл Ерыганов 21.02.2013, 16:41

Все одно не розумію. А крім того, стріляти без прокручення барабану — нечесно, адже наші шанси будуть більші за першого гравця.

Кирилл Ерыганов 21.02.2013, 16:49

Про більярдні кулі — згоден, тепер зрозумів. Приношу вибачення.

Богдан Федис 21.02.2013, 16:53

Ну, така умова задачі, із пісні слів не викинеш ))

Ви намалюйте барабан, так зрозуміти буде набагато легше.

Кирилл Ерыганов 22.02.2013, 09:20

Уже зрозумів, Богдане. Фактично — правильно, математично — не зовсім коректно, бо ми спираємося не на випадіння певної камери, а на положення барабану після осічки першого гравця.

Михаил Козак 26.02.2013, 14:38

з барабоаном чиста математика, теорія імовірностей.
коли крутиш барабан імовірність що не трапиться куля 4\6=0,66
а імовірність того що після пустої лунки буде йти знову пуста лунка 3 з 4 = 3\4=0,75

Назар Грицько 26.02.2013, 18:13

На мою думку не зовсім вірно.
Згідно вашого підходу виходить, що до нажаття на курок ймовірність випаду пустої лунки 4/4, тобто 1
Я вважаю краще знову прокрутити, тоді ймовірність що випаде пуста лунка 4/6= 0,67
Інакше: ймовірність того, що лунка буде пустою 3/5= 0,6, адже залишається 3 пустих і 2 повні
Тобто краще прокручувати барабан.

Дмитрий Колесник 27.02.2013, 08:36

На самом деле мы не знаем, на какой камере остановился барабан после первого спуска, но при прокручивании барабана шанс выпадения пустой камеры 4/6, а без прокручивания после спуска — 3/4, так как холостой спуск возможен только на пустой камере, а их 4. Нас не устраивает только вариант последней камеры перед двумя заряженными.

Люсьена Асланова 04.01.2020, 04:54

Прокрутить барабан в один челчек в обратную сторону т.е на отстреленую лунку 100%

Александр Губарец 25.02.2013, 22:40

«Русская рулетка»
вообще-то в задаче исключен вариант осечки у первого игрока. поэтому разницы что раскрученный барабан что нет — разницы никакой.

Богдан Боярко 26.02.2013, 00:11

Кирилл,вдумайся внимательно,по поводу шаров в ответе написано верно(то есть необходимо 2 действия).первое действие-сравнить группы с 3 шарами.2 действие будет зависеть от результата 1-го.Если в одной из тройных групп-необходимо в более тяжелой группе сравнить 2 из 3 шара(если два шара одинаковы,то тяжелый по логике будет третий.или один из взвешиваемых шаров,если он попал туда)Если группы оказались одинакового веса,то тяжелый шар в группе из 2х шаров,и сравнить их тоже-второй шаг.Что непонятного?

Андрей Гарматюк 26.02.2013, 08:04

Невнимательно прочитал решение-прочитай ещё раз. Там всё правильно — 2 взвешывания.

Кирилл Ерыганов 26.02.2013, 08:57

Народ, вы читать не умеете? Я давно признал свою ошибку! Перечитайте мою переписку с Богданом Федисом.

Люсьена Асланова 04.01.2020, 04:58

Можно одним шагом,если не важна точная цифра в разнице.просто наклонить. Поверхность и вуаля !самый тяжелый остановиться дальше.

Андрей Балык 26.02.2013, 12:20

Попробуйте провести эксперимент(или включите воображение) так, как предложено автором. У Вас получится за 2 взвешивания.

Елена Тыховлис 26.02.2013, 13:06

про шары — ответ в статье правильный!
Первое взвешивание:
Вначале взвешиваются на весах 2 группы шаров «3шт_3шт». Если весы уравнились, то будет второе взвешивание (А). Если весы НЕуравнились, то будет второе взвешивание (Б).

Второе взвешивание (А)
Взвешиваем оставшиеся 2 шара (которые еще не были на весах) «1шт_1шт» Там точно один будет тяжелее!

Второе взвешивание (Б)
Взвешиваем ЛЮБЫЕ 2 шара «1шт_1шт» из группы, которая перевесила на весах, при первом взвешивании. Есл весы уравнились при втором взвешивании (Б) — значит более тяжелый третий, невзвешенный шар из группы. Если перевес есть — значит вот он, тяжелый шар! 🙂

Все равно — 2 взвешивания!

Кирилл Ерыганов 27.02.2013, 09:39

Вы не умеете читать? Еще раз смотрим выше, я признал свою ошибку.

Vladimir Kulikov 26.02.2013, 19:36

Петро Однорог 05.03.2013, 12:08

Я теж вирішив задачу як ви. За три зважування. (дві четвірки і потім по черзі дві пари).
А потім прочитав рекомендацію статті. Дійсно їх метод два зважування вірний. Просто друге зважування дасть відповідь який шар вам потрібний навіть якщо він і не буде покладений на ваги. В статі правильно вказаний метод.

Сергей Кудлай 14.03.2013, 10:12

неправильно что за шары что за револьвер

Надія К. 29.05.2013, 16:44

Здравствуйте! Проходила сегодня собеседование в компанию Apple. Мне задали вопрос о теннисных мячах и автобусе, вот только не о том сколько их поместится, а как посчитать разбросанные по желтому автобусу «Богдан» мячики. )))))) Не ожидала, так как впервые столкнулась с подобным. и только придя домой начала искать информацию о подобных вопросах. Теперь то я уже почти «умная», а на собеседовании ответила: «Начала бы с начала автобуса, и продвигалась до конца перещитывала б те злощасные мячи. » (по идее они ж просто разбросаны по полу). Опять вопрос — а если собьетесь? Ответ что это маловероятно рекрутера не устроил. Ну я и ответила что начну сначала. В итоге несколько секунд тишины с его стороны! Наверное обдумывал что бы ему хотелось на обед 😉
Вот теперь сижу дома с пониманием того что я полный ЛОХ, и не видеть мне рабочего места в этой компании как собственных ушей.
Жаль, зп там достойная, да и сама компания много чего стоит.

Роман Авдеев 02.06.2013, 11:48

Надія К.
А Вы точно уверены что Apple чего-то стоит?)) Это не отделение в США либо Европе, зарплаты там такие же или даже меньше, чем в рядовом магазине электроники, т.к. нюанс что в рядовом магазине оборот намного больше, ведь там продают продукцию разной ценовой категории, а не так как в Apple.
Как бы наш народ не любил понтоваться, но возможность выложить за несчастный ноутбук 15 тыс. грн. мало у кого есть.
Не ведитесь на громкое имя, как Вы сами видели на собеседовании, там работают такие же бараны HRы, перечитавшие иностранной псевдонаучной литературы по персоналу.