решение задач | C++ для приматов

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

#include <iostream>
int main() {
    long A, B, C;
    std::cin >> A >> B >> C;
    std::cout << (A - 1) + A * (B - 1) + A * B * (C - 1);
    return 0;
}

#include <iostream>

int main() {

long A, B, C;

std::cin >> A >> B >> C;

std::cout << (A - 1) + A * (B - 1) + A * B * (C - 1);

return 0;

}

Моделирование и системный подход. Вся супер идея решения состоит в наблюдении, что разрезая что-либо несколькими параллельными разрезами, вы получаете на один кусок больше чем было разрезов. Например, один разрез — два куска. Правда сложно заметить?
Да, придется понаблюдать за тем, что происходит если производить дополнительные разрезы в перпендикулярном направлении. Т.е. после разрезов в одной плоскости получаются пластины, во второй — соломка, в третьей — кубики. Понаблюдайте:

Читает условие — иногда несколько раз и обязательно все буквы. Отделяет существенное от неважного.
Представляет себе описанный процесс и его конечный результат отсекая ненужные для решения детали.
Пытается описать формулами процесс или результат. Упрощает формулы.
И наконец — кладет руки на клавиатуру и кодирует.

Возможно Вы заметили, что в первом коротком решении мы не выполнили собственную рекомендацию — не упростили формулу. Действительно, хотя все измерения абсолютно равнозначны, формула не выглядит симметричной. Это сделано чтобы понятнее был процесс вывода формулы. Первое слагаемое [latex]A-1[/latex] в общем числе разрезов показывает как мы резали перпендикулярно оси [latex]Ox[/latex]. Мы сделали [latex]A-1[/latex] разрез и получили [latex]A[/latex] пластин. Второе слагаемое [latex]A\cdot\left(B-1\right)[/latex] показывает как мы резали перпендикулярно оси [latex]Oy[/latex]. Мы сделали [latex]B-1[/latex] разрез в каждой из [latex]A[/latex] пластин полученных при предыдущей серии разрезов. И наконец, на последнем этапе, мы режем каждый из [latex]A\cdot B[/latex] брусочков на кубики при помощи [latex]С-1[/latex] разрезов. Получаем [latex]A\cdot B\cdot\left(C-1\right)[/latex] разрезов. Конечно, результат не должен измениться, если резать в каком-то другом порядке. Если раскрыть скобки и привести подобные мы увидим короткую симметричную относительно измерений формулу.

[latex]\left(A-1\right) + A \cdot \left(B-1\right) + A \cdot B \cdot \left(C-1\right) = ABC-1[/latex]

Аналитический подход. Эта новая формула может быть получена другими очень простыми рассуждениями.

Вначале был один большой кусок. После каждого разреза количество кусочков увеличивается на 1. В самом конце получится [latex]ABC[/latex] кусочков, значит разрезов было на 1 меньше — [latex]ABC-1[/latex].

Это последнее рассуждение демонстрирует подход к которому нужно стремиться — все просто, ясно, лаконично. Не всегда он срабатывает. Часто именно моделирование и системный подход с разбиением на системы и подсистемы позволяет найти решение. Но обычно этот путь более громоздкий. Зато аналитический иногда похож на некий волшебный трюк, когда задача с хлопком исчезает и на её месте появляется ответ. Подробнее об этом, например, здесь…

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

Код программы с новой формулой

#include <iostream>
using namespace std;
int main() {
	long A, B, C;
	cin >> A >> B >> C;
	cout << A * B * C - 1;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long A, B, C;

cin >> A >> B >> C;

cout << A * B * C - 1;

return 0;

}

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

Const NMax = 30;
Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;
Var S : String;
    M, N, R, F, K : DlChislo;
    I, MaxF : Word;
    Logic : Boolean;
    c:char;
Procedure Zero(Var A : DlChislo);
Var I : Integer;
  Begin
    For I := 1 To NMax Do A[i] := 0;
  End;
Function Dlina(C : DlChislo) : Integer;
Var I : Integer;
Begin
   I := NMax;
   While (I > 1) And (C[i] = 0) Do I := I - 1;
   Dlina := I
End;
Procedure Print(A : DlChislo);
Var I : Integer;
Begin
    For I := Dlina(A) DownTo 1 Do Write(A[i] : 1);
    WriteLn;
End;
Procedure Translate(S : String; Var A : DlChislo;
                    Var OK : Boolean);
Var I : Word;
Begin
   Zero(A); I := Length(S); OK := True;
   While (I >= 1) And OK Do
   Begin
      If S[i] In ['0'..'9']
      Then A[Length(S) - I+ 1] := Ord(S[i]) - 48
      Else OK := False;
      I := I - 1
   End
End;
Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);
Var I, J : Integer; P : Digit; VspRez : 0..99;
Begin
  Zero(C);
  For I := 1 To Dlina(A) Do
  Begin P := 0;
        For J := 1 To Dlina(B) Do
        Begin
          VspRez := A[i] * B[J] + P + C[I + J - 1];
    C[I + J - 1] := VspRez Mod 10;
    P := VspRez Div 10
  End;
        C[I + J] := P
   End
End;
Begin
     s:='';
     read(c);
     while c in ['0'..'9'] do begin s:=s+c; read (c); end;
     Translate(S, M, Logic);
     s:='';
     read(c);
     while c in ['0'..'9'] do begin s:=s+c; read (c); end;
     Translate(S, N, Logic);
     s:='';
     read(c);
     while c in ['0'..'9'] do begin s:=s+c; read (c); end;
     Translate(S, K, Logic);
   Multiplication(M, N, R);
   Multiplication(R, K, R);
   i:=1;
   while not(r[i]-1>=0) do begin r[i]:=9; i:=i+1; end;
   r[i]:=r[i]-1;
   Print(R);
End.

Const NMax = 30;

Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;

Var S : String;

M, N, R, F, K : DlChislo;

I, MaxF : Word;

Logic : Boolean;

c:char;

Procedure Zero(Var A : DlChislo);

Var I : Integer;

Begin

For I := 1 To NMax Do A[i] := 0;

End;

Function Dlina(C : DlChislo) : Integer;

Var I : Integer;

Begin

I := NMax;

While (I > 1) And (C[i] = 0) Do I := I - 1;

Dlina := I

End;

Procedure Print(A : DlChislo);

Var I : Integer;

Begin

For I := Dlina(A) DownTo 1 Do Write(A[i] : 1);

WriteLn;

End;

Procedure Translate(S : String; Var A : DlChislo;

Var OK : Boolean);

Var I : Word;

Begin

Zero(A); I := Length(S); OK := True;

While (I >= 1) And OK Do

Begin

If S[i] In ['0'..'9']

Then A[Length(S) - I+ 1] := Ord(S[i]) - 48

Else OK := False;

I := I - 1

End

End;

Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);

Var I, J : Integer; P : Digit; VspRez : 0..99;

Begin

Zero(C);

For I := 1 To Dlina(A) Do

Begin P := 0;

For J := 1 To Dlina(B) Do

Begin

VspRez := A[i] * B[J] + P + C[I + J - 1];

C[I + J - 1] := VspRez Mod 10;

P := VspRez Div 10

End;

C[I + J] := P

End

End;

Begin

s:='';

read(c);

while c in ['0'..'9'] do begin s:=s+c; read (c); end;

Translate(S, M, Logic);

s:='';

read(c);

while c in ['0'..'9'] do begin s:=s+c; read (c); end;

Translate(S, N, Logic);

s:='';

read(c);

while c in ['0'..'9'] do begin s:=s+c; read (c); end;

Translate(S, K, Logic);

Multiplication(M, N, R);

Multiplication(R, K, R);

i:=1;

while not(r[i]-1>=0) do begin r[i]:=9; i:=i+1; end;

r[i]:=r[i]-1;

Print(R);

End.

Я позаимствовал это решение с форума, но у нас имеются и свои подобные решения. Они работают правильно. Вот только долго. Но это еще не всё. Представляете количество времени потраченное на его качественную отладку и тестирование? А в реальных проектах этот код возможно потом придется долгие годы поддерживать и переписывать на новые языки программирования!
Чтобы разобраться как работает это второе решение достаточно посмотреть следующее видео

Пожалуйста! Не решайте задачи так!

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: решение задач

Как не нужно решать задачи

Related Images: