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

Зелёный куб

У вас есть куб со стороной 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.

import java.util.ArrayList;
 
public class Edit_Distance {
    static int dp[][];
 
    // Создаем коллекцию хранения всех наборов операций
    static ArrayList<ArrayList > arrs =
                              new ArrayList<ArrayList >();
 
    // Функция для вывода всех вариантов преобразований
    static void printAllChanges(String s1,
                                String s2, ArrayList changes)
    {
 
        int i = s1.length();
        int j = s2.length();
 
        // Перебираем строку до конца
        while (true) {
 
            if (i == 0 || j == 0) {
 
                //  Добавляем список в коллекцию
                arrs.add(changes);
                break;
            }
 
            // Проверяем, одинаковы ли символы
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                i--;
                j--;
            }
 
            else {
                boolean if1 = false, if2 = false;
 
                // Если тип операции «замена»
                if (dp[i][j] == dp[i - 1][j - 1] + 1) {
 
                    // Добавляем операцию в коллекцию
                    changes.add("Change " + s1.charAt(i - 1)
                                + " to " + s2.charAt(j - 1));
                    i--;
                    j--;
 
                    // Помечаем условие как верное
                    if1 = true;
                }
 
                // Если тип операции «удаление»
                if (dp[i][j] == dp[i - 1][j] + 1) {
                    if (if1 == false) {
                        changes.add("Delete " + s1.charAt(i - 1));
                        i--;
                    }
                    else {
                        // Если предыдущий вариант был верным,
                        // создаем новую копию списка
                        ArrayList changes2 = new ArrayList();
                        changes2.addAll(changes);
 
                        // Удаляем последнюю операцию
                        changes2.remove(changes.size() - 1);
 
                        // Добавляем новую операцию
                        changes2.add("Delete " + s1.charAt(i));
 
                        // Запускаем функцию для оставшихся символов
                        printAllChanges(s1.substring(0, i),
                                        s2.substring(0, j + 1), changes2);
                    }
 
                    if2 = true;
                }
 
                // Добавление символа
                if (dp[i][j] == dp[i][j - 1] + 1) {
                    if (if1 == false && if2 == false) {
                        changes.add("Add " + s2.charAt(j - 1));
                        j--;
                    }
                    else {
 
                        ArrayList changes2 = new ArrayList();
                        changes2.addAll(changes);
                        changes2.remove(changes.size() - 1);
                        changes2.add("Add " + s2.charAt(j));
 
                        // Рекурсивно вызываем функцию для остальных шагов
                        printAllChanges(s1.substring(0, i + 1),
                                        s2.substring(0, j), changes2);
                    }
                }
            }
        }
    }
 
    // Функция для вычисления DP матрицы
    static void editDP(String s1, String s2)
    {
        int l1 = s1.length();
        int l2 = s2.length();
        int[][] DP = new int[l1 + 1][l2 + 1];
 
        // Инициализируем максимальным количеством правок
        for (int i = 0; i <= l1; i++)
            DP[i][0] = i;
        for (int j = 0; j <= l2; j++)
            DP[0][j] = j;
 
        // Вычисляем матрицу DP
        for (int i = 1; i <= l1; i++) {
            for (int j = 1; j <= l2; j++) {
 
                // Если символы одинаковые, изменений не требуется
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    DP[i][j] = DP[i - 1][j - 1];
                else {
 
                    // Возможны как минимум 3 операции
                    DP[i][j] = min(DP[i - 1][j - 1],
                                   DP[i - 1][j], DP[i][j - 1])
                               + 1;
                }
            }
        }
 
        // Инициализируем глобальный массив
        dp = DP;
    }
 
    // Функция для нахождения минимального количества операций
    static int min(int a, int b, int c)
    {
        int z = Math.min(a, b);
        return Math.min(z, c);
    }
    static void printWays(String s1, String s2,
                          ArrayList changes)
    {
 
        // Функция для вывода всех операций в последовательности 
        printAllChanges(s1, s2, new ArrayList());
 
        int i = 1;
 
        for (ArrayList ar : arrs) {
            System.out.println("\nMethod " + i++ + " : \n");
            for (String s : ar) {
                System.out.println(s);
            }
        }
    }
 
    public static void main(String[] args) throws Exception
    {
        String s1 = "abcdef";
        String s2 = "axcdfdh";
 
        // Вычисляем матрицу DP
        editDP(s1, s2);
 
        // Выводим все варианты преобразований
        printWays(s1, s2, new ArrayList());
    }
}

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

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

Если вы думаете, что 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.

Подобрали два теста для вас:
— А здесь можно применить блокчейн?
Серверы для котиков: выберите лучшее решение для проекта и проверьте себя.