Написать пост

Режем кубы, преобразовываем строки, считаем квадраты: подборка задач для программистов

Аватар Андрей Приб

Зелёный куб, строки и квадраты на шахматной доске — встречайте новую подборку в нашем цикле задачек!

Обложка поста Режем кубы, преобразовываем строки, считаем квадраты: подборка задач для программистов

Зелёный куб

У вас есть куб со стороной 4 см, покрашенный зеленой краской со всех сторон. Вы разрезаете этот куб на маленькие кубики со стороной 1 см. У этих новых кубиков будет либо 3 зеленые стороны, либо 2 зеленые стороны, либо 1, либо вообще ни одной. Все кубики помещаются в урну и тщательно перемешиваются, затем случайным образом выбирается один. Он подбрасывается как игральная кость. Какова вероятность, что он приземлится зеленой стороной вверх?

Оригинал задачи на английском языке

You have a 4-cm cube which is coated with green paint on all six sides. You cut this big green cube into individual 1-cm cubes. These new one-cm cubes will have either three green sides, two green sides, one green side, or no green sides. All of these little cubes are placed into an urn, are thoroughly mixed, and one selected at random. This chosen cube is then rolled like a die. What is the probability that it lands with a green face up?

Решение задачи на русском языке

При разрезании большого куба получится 64 маленьких (4 x 4 x 4):

  • 8 кубиков из середины будут без зеленых граней;
  • 8 угловых кубиков будут иметь по 3 зеленых грани;
  • 24 кубика, расположенные на ребрах, будут иметь по 2 зеленых грани;
  • и 24 кубика будут иметь по одной зеленой грани.

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

Вероятность, что кубик приземлится на зеленую сторону, — 25%.

Решение задачи на английском языке

When the larger cube is cut up, 64 smaller cubes are created (4 x 4 x 4):

  • The 8 cubes that were in the middle of the larger cube have no green faces;
  • The 8 cubes that were at the corners have three green faces;
  • There are 24 cubes that were on the edges and have two green faces;
  • Finally there are 24 cubes that have just one painted face.

One of the 64 cubes is selected at random, and since we know how many of each «flavor» of cubes there are, we can calculate the probability of each kind being selected. Then, since we know the number of painted faces on each kind of cube, we can find the overall probability.

 

There is a 25% that the cube will roll to green.

Способы преобразования одной строки к другой

Даны 2 строки: str1 и str2; задача — вывести все возможные варианты преобразования str1 в str2. К str1 применимы операции:

  • вставки;
  • удаления;
  • замены.

Все операции имеют одинаковую стоимость. Задача — вывести все варианты преобразования str1 в str2 с использованием минимального количества шагов (операций), где вариантом ответа является последовательность операций.

Примеры:

Вход: str1 = «abcdef», str2 = «axcdfdh»

Выход:

Вариант 1:

  • Вставить h;
  • Заменить f на d;
  • Заменить e на f;
  • Заменить b на x.

Вариант 2:

  • Заменить f на h;
  • Вставить d;
  • Заменить e на f;
  • Заменить b на x.

Вариант 3:

  • Заменить f на h;
  • Заменить e на d;
  • Вставить f;
  • Заменить b на x.
Оригинал задачи на английском языке

Given two strings str1 and str2, the task is to print the all possible ways to convert «str1» into «str2».

Below are the operations that can be performed on «str1»:

  1. Insert.
  2. Remove.
  3. Replace.

All of the above operations are of equal cost. The task is to print all the various ways to convert «str1» into «str2» using the minimum number of edits (operations) required, where a «way» comprises of the series of all such operations required.

Examples:

Input: str1 = «abcdef», str2 = «axcdfdh»

Output:

Method 1:

  • Add h;
  • Change f to d;
  • Change e to f;
  • Change b to x.

Method 2:

  • Change f to h;
  • Add d;
  • Change e to f;
  • Change b to x.

Method 3:

  • Change f to h;
  • Change e to d;
  • Add f;
  • Change b to x.
Решение задачи на русском языке

Создадим коллекцию строк для хранения необходимых операций. Эта коллекция может быть реализована через vector строк в C++ или List строк в Java. Добавим операции в эту коллекцию. Затем создадим коллекцию таких коллекций, в которой будут храниться несколько методов (наборов строковых операций).

Else-if используются для проверки наследования от DP[i][j]. Проверим все условия, на случай, если существует более одного способа получить элемент коллекции. Если существует, создадим новую коллекцию из предыдущей, удалим последнюю операцию, добавим новую операцию и запустим функцию с новым списком. Таким образом мы будем создавать новый список каждый раз, когда обнаружится новый способ преобразования, получая каждый раз новый метод.

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

Решение задачи на английском языке

Create a collection of strings that will store the operations required. This collection can be a vector of strings in C++ or a List of strings in Java. Add operations just like printing them before to this collection. Then create a collection of these collections which will store the multiple methods (sets of string operations).

Else-if are used to check from where we derived the DP[i][j] from. Now, check all If’s to see if there were more than 1 ways you could obtain the element. If there was, we create a new collection from before, remove the last operation, add this new operation and initiate another instance of this function with this new list. In this manner, add new lists whenever there was a new method to change str1 to str2, getting a new method every time.

On reaching the end of either string, add this list to the collection of lists, thus completing the set of all possible operations, and add them.

Код
			
		

Квадраты на шахматной доске

Сколько квадратов на шахматной доске?

Режем кубы, преобразовываем строки, считаем квадраты: подборка задач для программистов 1

Если вы думаете, что 64, — подумайте еще раз!

Учли ли вы квадраты, которые образованы комбинацией клеток (2×2, 3×3, 4×4 и т.д.)?

Оригинал задачи на английском языке

How many squares are present on the chess board?

If your first thought was 64, think again!

Did you think about all the squares that are formed by combining smaller squares on the chess board (2×2, 3×3, 4×4 squares and so on)?

Решение задачи на русском языке

Квадрат 1×1 может быть расположен в 8 позициях по горизонтали и в 8 — по вертикали, всего 64 квадрата. Рассмотрим квадрат 2×2. Для него есть 7 горизонтальных и 7 вертикальный позиций. Почему? Потому что выбрать 2 соседних клетки из 8 можно только 7 способами. Получаем 7 x 7 = 49 квадратов 2×2. Аналогично для квадратов 3×3: 6 x 6 = 36 вариантов. Итак:

  • 1×1: 8×8 = 64 квадрата;
  • 2×2: 7×7 = 49 квадратов;
  • 3×3: 6×6 = 36 квадратов;
  • 4×4: 5×5 = 25 квадратов;
  • 5×5: 4×4 = 16 квадратов;
  • 6×6: 3×3 = 9 квадратов;
  • 7×7: 2×2 = 4 квадрата;
  • 8×8: 1×1 = 1 квадрат.

1^2 + 2^2 + 3^2 + . . . n ^2

Всего = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204 квадрата.

Решение задачи на английском языке

A 1×1 square can be placed on the chess board in 8 horizontal and 8 vertical positions, thus making a total of 8 x 8 = 64 squares. Let’s consider a 2×2 square. There are 7 horizontal positions and 7 vertical positions in which a 2×2 square can be placed. Why? Because picking 2 adjacent squares from a total of 8 squares on a side can only be done in 7 ways. So we have 7 x 7 = 49 2×2 squares. Similarly, for the 3×3 squares, we have 6 x 6 = 36 possible squares. So here’s a break down:

  • 1×1 8 x 8 = 64 squares;
  • 2×2 7 x 7 = 49 squares;
  • 3×3 6 x 6 = 36 squares;
  • 4×4 5 x 5 = 25 squares;
  • 5×5 4 x 4 = 16 squares;
  • 6×6 3 x 3 = 9 squares;
  • 7×7 2 x 2 = 4 squares;
  • 8×8 1×1 = 1 square.

1^2 + 2^2 + 3^2 + . . . n ^2

Total = 64 + 49 + 36 + 25 + 16 + 9 + 4 + 1 = 204 squares.

Следите за новыми постами
Следите за новыми постами по любимым темам
10К открытий10К показов