Опровержение мудреца. Анализируем предложенный алгоритм

Опровержение мудреца. Анализируем предложенный алгоритм

Цель работы: Написать развлекательно-обучающую публикацию по языку программирования java.

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

В социальных сетях, довольно часто, встречается такой мем.



Рис 1.

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

Зная язык java мы можем с легкостью проверить все частные случаи. Мы можем выяснить в каких случаях алгоритм работает правильно и в каких такой алгоритм не выполняется. Мы с вами спроектируем и напишем программу для вывода всех утверждений для двузначных чисел.
Посчитаем количество правильных и не верных утверждений. Мы не будем сильно «заморачиваться» с наследованием и интерфейсами. Спроектируем и реализуем класс, в котором будет выполняться работа по проверке и подсчету. Сформулируем цель нашей работы.

Цель работы: Спроектировать и реализовать класс, который проверит приведенный выше алгоритм.

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

На рисунке мы видим алгоритм вычислений. Назовем левую часть искомого числа, ту что отмечена красным begin. Назовем правую часть искомого числа(отмечена на рисунке синим) – end.


begin = 100 — ( 100 — a + 100 — b ).
end = (100 — a) * (100 – b).

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

Назовем наш класс «опровержение мудреца» («denial of the sage») — DenialOfTheSage. Расположим наш класс в пакете «denialOfTheSage01».

/*
 * Опровержение мудреца
 */
package denialOfTheSage01;

/**
 *
 * @author  Ar20L80
 */
public class DenialOfTheSage {

    public static void main(String[] args) {

    }
}

Нам понадобятся переменные для подсчета количества правильных ответов и для подсчета количества неправильных ответов алгоритма. Назовем наши переменные countSageIsRight и countSageIsWrong. Выберем тип переменных int. Переменные целого типа.

int countSageIsRight = 0; // количество правильных ответов
int countSageIsWrong = 0; // количество неправильных ответов

Введем еще одну переменную которая будет показывать общее количество ответов. Назовем переменную countAnswer.

int countAnswer = 0; // общее количество ответов

Мы присвоили переменным значение 0, потому как в самом начале ответов никаких нет. Для обозначение первого и второго двузначного числа мы будем использовать переменные x и y.

int x,y; // первое и второе двузначное число, которое мы используем

Для вывода чисел и для нашего удобства напишем метод вывода переменных x и y. Назовем наш метод — showXY:

public static void showXY(int x, int y) {
        System.out.print("для x = " + x + "  y = " + y + " ");
    }

Напишем два метода для вывода ошибается наш «мудрец» или нет в каком-то конкретном случае.

public static void showSageIsTrue() {
        System.out.println("Правда!");
    }
 
    public static void showSageIsFalse() {
        System.out.println("Неправда!");
    }

В программе нам нужно перебрать все двузначные числа от десяти до 99-ти включительно. Закрытый интервал: [10,99]. Напишем цикл в котором будем перебирать наши двузначные числа.

for (x = 10; x <= 99; x++) { //перебираем x цикле от 10 до 99 включительно
            for (y = 10; y <= 99; y++) { //перебираем y цикле от 10 до 99 включительно
                countAnswer++;
                System.out.print(countAnswer + ".   "); //вывод номера ответа
                showXY(x, y); // вывод на экран для x =  y =
                if (x * y == result(x, y)) {
                    showSageIsTrue(); // выводим "Правда"
                    countSageIsRight++; // увеличиваем счетчик "правды" на единицу
                } else {
                    showSageIsFalse(); // выводим "Неправда"
                    countSageIsWrong++;// увеличиваем счетчик "неправды" на единицу
                }
            }
        }
		

Размещаем его в методе main. Напишем метод вычисления результата. Реализуем предложенный алгоритм.

public static int result(int x, int y) {// результат вычисления мудреца по предложенному алгоритму

        int minus_x = 100 - x;
        int minus_y = 100 - y;
        int plus = minus_x + minus_y;
        int hundr_minus_summ = 100 - plus;

        int begin = hundr_minus_summ; // начало числа
        int end = minus_x * minus_y; // окончание числа
        String strResult = String.valueOf(begin) + String.valueOf(end); // объединяем два числа в строке

        int result = Integer.parseInt(strResult);
        return result;
    }

Пишем небольшой тест, чтобы удостовериться, что объедение строк работает правильно:

 public class TestCont {

    public static void main(String[] args) {
        int num = 0;
        String strResult;
        for (int x = 10; x <= 99; x++) { //перебираем x цикле от 10 до 99 включительно
            for (int y = 10; y <= 99; y++) { //перебираем y цикле от 10 до 99 включительно
                num++;
                strResult = String.valueOf(x) + String.valueOf(y); // объединяем два числа в строке
                System.out.println(num + ". " + strResult);

            }
        }
    }
}

Однако если результат будет меньше десяти, то у нас получится ошибка.
Простое объединение может работать неправильно.
В предложенном мудрецом алгоритме левая часть считается по формуле (отмечена красным):
100 — ( 100-a + 100 — b ) = 100 — 100 + a — 100 + b = a -100 + b = a + b — 100 = begin;

Правая часть(отмечена синим):
(100 — a) * (100 — b) = 10000- 100b -100a +ab = end;

Однако, простое объединение не всегда дает верный результат.
Перепишем наш метод так, и добавим ведущий 0 если второе число меньше 10.
Здесь я переименовал метод

result(int x, int y)... 

на

sageSaid(int x, int y) ...

 private static int sageSaid(int x, int y) {// результат вычисления мудреца, мудрец сказал

        int begin = x + y - 100; // начало числа, первая часть обозначенная на рисунке красным
        int end = (100 - x) * (100 - y); // окончание числа, первая часть обозначенная на рисунке синим

        String strResult;
        if (end < 10) {
            strResult = String.valueOf(begin).concat("0").concat(String.valueOf(end)); // объединяем три числа в строке
        } else {
            strResult = String.valueOf(begin).concat(String.valueOf(end)); // объединяем два числа в строке
        }

        int result = Integer.parseInt(strResult); // переводим стоку в int
        return result;
    }
  

Мы знаем, что a * b = b * a. Это означает, что мы проводим лишние вычисления, которые у нас повторяются. Перепишем наш цикл:

for (x = 10; x <= 99; x++) {
            for (y = x; y <= 99; y++) {
...

Перепишем вывод результата:

...
 System.out.println("Мудрец сказал правду " + countSageIsRight + " раз из " + countAnswer);
        System.out.println("Мудрец сказал неправду " + countSageIsWrong + " раз из " + countAnswer);
...

в результате у нас получилась такая программа:

/*
 Публикация на https://habr.com/
 */
package denialOfTheSage04;

/**
 *
 * @author  Ar20L80
 */
public class DenialOfTheSage {

    public static void main(String[] args) {
        int countSageIsRight = 0; // количество правильных ответов
        int countSageIsWrong = 0; // количество неправильных ответов
        int countAnswer = 0; // общее количество ответов
        int x, y; // первое и второе двузначное число, которое мы используем

        for (x = 10; x <= 99; x++) {
            for (y = x; y <= 99; y++) {
                countAnswer++;
                System.out.print(countAnswer + ".   "); //вывод номера ответа
                showXY(x, y); // вывод на экран для x =  y =
                if (x * y == sageSaid(x, y)) {
                    showSageIsTrue(); // выводим "Правда"
                    countSageIsRight++; // увеличиваем счетчик "правды" на единицу
                } else {
                    showSageIsFalse(); // выводим "Неправда"
                    countSageIsWrong++;// увеличиваем счетчик "неправды" на единицу
                }

            }
        }

        System.out.println();
        System.out.println("Итог: ");
        System.out.println("Мудрец сказал правду " + countSageIsRight + " раз из " + countAnswer);
        System.out.println("Мудрец сказал неправду " + countSageIsWrong + " раз из " + countAnswer);

    }

    private static void showXY(int x, int y) { // метод вывода переменных x и y
        System.out.print("для x = " + x + "  y = " + y + " ");
    }

    private static void showSageIsTrue() { // вывод на экран "Правда!"
        System.out.println("Правда!");
    }

    private static void showSageIsFalse() {// вывод на экран "Неправда!"
        System.out.println("Неправда!");
    }

    private static int sageSaid(int x, int y) {// результат вычисления мудреца, мудрец сказал

        int begin = x + y - 100; // начало числа, первая часть обозначенная на рисунке красным
        int end = (100 - x) * (100 - y); // окончание числа, первая часть обозначенная на рисунке синим

        String strResult;
        if (end < 10) {
            strResult = String.valueOf(begin).concat("0").concat(String.valueOf(end)); // объединяем три числа в строке
        } else {
            strResult = String.valueOf(begin).concat(String.valueOf(end)); // объединяем два числа в строке
        }

        int result = Integer.parseInt(strResult); // переводим стоку в int
        return result;
    }

}

Вывод программы:

 run:
1.   для x = 10  y = 10 Неправда!
2.   для x = 10  y = 11 Неправда!
3.   для x = 10  y = 12 Неправда!
...
8099.   для x = 99  y = 98 Правда!
8100.   для x = 99  y = 99 Правда!
Итог: 
Мудрец сказал правду 273 раз из 4095
Мудрец сказал неправду 3822 раз из 4095

Здесь я добавляю лидирующие нули ко второй части числа, второй половине отмеченной на рисунке синим.

strResult = String.valueOf(begin).concat("0") ...

Этого мудрец нам не говорит делать. То есть, если буквально понимать предложенный алгоритм, то окончание числа просто добавляется без лидирующих нулей. Этот феномен, «подразумевание» условий задачи, довольно часто приводит к непониманию между программистами и заказчиками. Хорошо и грамотно написанное техническое задание намного, можно сказать в разы, ускоряет процесс разработки. Но писать ТЗ — это настоящее искусство, которое может прийти только с опытом. Вы можете не добавлять лидирующие нули и убрать условие

if (end < 10) { ...

Тогда у вас получится такой результат.

Итог: 
Мудрец сказал правду 260 раз из 4095
Мудрец сказал неправду 3835 раз из 4095

Вы можете самостоятельно улучшить код. Рефакторинг это уже второе дело. Главное, что мы с вами получили на начальном этапе работающую программу. Мы увидели для каких двузначных чисел предложенный нам алгоритм выполняется правильно. Мы посчитали, что количество неправильных ответов 3822, количество правильных ответов 273 из 4095. Алгоритм по прежнему дает сбои. Это происходит в случаях когда вторая часть искомого числа больше 99-ти. Вы, также, можете переписать программу не используя тип String для объединения результата, а используя только int.

Доработаем алгоритм «мудреца», чтобы получить правильные вычисления.
У нас получится не простая конкатенация(соединение) двух чисел, а сложение этих чисел и умножение левой части искомого числа на 100.

Тогда мы получим верное решение, но алгоритм будет выглядеть по другому.

begin = (100-(100-a) + (100-b))*100.
end = (100-a)*(100-b).

result = begin+end.

Мы можем модифицировать нашу программу и написать новый метод:

private static int sageSaid2(int x, int y) {
     
        int begin = x + y - 100; // начало числа
        int end = (100 - x) * (100 - y); // окончание числа
        int result = 100*begin + end;
        return result;
     }

В методе main() запишем вместо

 if (x * y == sageSaid(x, y))

,

if (x * y == sageSaid2(x, y))

В этом случае алгоритм работает на все сто процентов.
Вывод программы, с доработанным нами алгоритмом:

4091.   для x = 97  y = 98 Правда!
4092.   для x = 97  y = 99 Правда!
4093.   для x = 98  y = 98 Правда!
4094.   для x = 98  y = 99 Правда!
4095.   для x = 99  y = 99 Правда!

Итог: 
Мудрец сказал правду 4095 раз из 4095
Мудрец сказал неправду 0 раз из 4095

Хотелось бы отметить, что сама иллюстрация расчетов, где присутствует мем(в нашем случае «мудрец») вырвана из некого контекста и когда-то была распространена в интернете. Цель публикации была не доказать или опровергнуть мудреца. Доказательство, можно сделать путем простых математических преобразований. Цель была немного попрактиковаться в написании простых программ на языке java. То есть, применить язык программирования на практике.

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