Задачки 1 и 2

Перейти вниз

Задачки 1 и 2 Empty Задачки 1 и 2

Сообщение автор Gudleifr в Вс Июн 11, 2017 11:01 am

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

ПЛАН СОБЕСЕДОВАНИЯ

Анкета
1. Оценка по математике.
2. Оценка по иностранному языку.
3. Оценка по русскому языку.
4. Основная (планируемая) специальность (для которой требуется знание ПК).
5. На сколько вырастет Ваш доход после освоения Вами ПК?
6. Любимая книга по компьютерам (математике).

* День 1 *

1. Вводная лекция (2 часа):
а) требования, предъявляемые рынком к операторам ЭВМ;
б) цели и задачи курса;
в) организация учебного процесса и требования дисциплины;
г) используемая литература;
д) ответы на вопросы абитуриентов.

2. Контрольная по математике (2 часа):
а) решение квадратного уравнения;
б) доказательство теоремы Пифагора;
с) (доп.) обоснование формулы решения квадратного уравнения.

3. Сочинение на тему "Как я вижу свою будущую работу на ЭВМ" (2 часа)

* День 2 *

4. Пробная лекция "Органы управления Windows" (2 часа)

5. Проверка конспектов и выполнение практического задания - поиск заданной темы в справочной системе MS Word (2 часа).

ПРИМЕЧАНИЕ: при выполнении этого и следующего пункта все свободные абитуриенты находятся в соседней аудитории под наблюдением ассистента.

6. Собеседование (5-15 минут на человека).

7. Общее собрание с оглашением статистики результатов (30 мин).

ПРИМЕЧАНИЕ: Если кто-нибудь из абитуриентов уже имел опыт программирования, то, вместо сочинения, ему будет предъявлена распечатка небольшой программы (см. ниже) и предложено проанализировать ее работу, не вводя в компьютер.

Распечатка тестовой программы (BASIC).

10 OPTION BASE 1: DIM D$(1025): D$(1)="ЭТО КОТ": I=1: ON ERROR GOTO 80
20 PRINT D$(I);: INPUT O$: O$=LEFT$(O$,1)
30 IF I<512 THEN IF D$(I*2)<>"" GOTO 70
40 IF O$="Д" OR O$="д" THEN PRINT "УРРА-А!": I=1: GOTO 20
50 D$(I*2+1)=D$(I): INPUT "А КТО ЭТО";O$: D$(I*2)="ЭТО "+O$
60 INPUT "ЧЕМ ОТЛИЧАЕТСЯ";D$(I): I=1: GOTO 20
70 IF O$="Д" OR O$="д" THEN I=I*2: GOTO 20: ELSE I=I*2+1: GOTO 20
80 PRINT "НЕ ХВАТАЕТ МОЗГОВ!": END

***

Последнюю задачку иногда ради хохмы предлагаю "современным программистам". Каков результат?
1. Большинство просто демонстративно отказываются иметь дело с "древним неправильным нечитаемым языком". Издевательски предлагают что-то прочесть/перевести на современных [экзотических] языках. После того, как им объяснят суть алгоритма, начинают находить "ошибки" и "недостатки образования оппонента".
2. Некоторое количество программистов честно переводят алгоритм на современный [любимый] язык "один в один". При этом, понятно, вся "бейсиковость" обычно остается. Если в привычной им парадигме присутствуют "структуры" и "объекты", можно наблюдать их применение (списковое представление дерева ответов, разные типы для вопросов и ответов, попытки инкапсулировать ввод/вывод...), всегда в ущерб понятности и правильности.
3. Очень немногие подхватывают идею и начинают ее "улучшать". Как тот аспирант, которому я втюхал эту программу (понятно, с надлежащей структурной обфускацией) в далекие студенческие годы за лабораторную по экспертным системам. Тогда большого труда стоило объяснить, что все просто "просто", но "очень просто".
4. Когда, после большого вызова "на слабо" я привожу ссылку на литературу и подтверждающий код, меня всегда банят.

Сам ржач находится по адресам
http://www.gamedev.ru/flame/forum/?id=226776
http://www.gamedev.ru/flame/forum/?id=226833


Последний раз редактировалось: Gudleifr (Вс Сен 03, 2017 11:38 am), всего редактировалось 2 раз(а)
Gudleifr
Gudleifr
Admin

Сообщения : 1095
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор Gudleifr в Вс Июн 11, 2017 11:24 am

Задания на исправление ошибок:

1. Допустим, я скачиваю из Сети журналы, постранично. Т.е. имеется огромная папка забитая файлами со схожими именами. Пришлось написать программку, ищущую дыры в нумерации. Все просто: dir или ls выдают имена файлов подряд, программе остается только подмечать дыры. Конкретные имена файлов почти не важны (см (б)).
а) Записать в нормальной форме примерное общее выражение "дыра между именами".
б) Какое свойство имен окажет наибольшее влияние на вид выражения (а)?

2. Когда-то для наглядности программы записывались в виде блок-схем. До последнего времени находятся изобретатели всяких универсальных методов построения всяких UML, XML-шаблонов, конструкторов и других средств наглядно показать "о чем идет речь". Каждому опытному программисту очевидно - для каждой по-настоящему новой задачи требуется свой особый язык блок-схем. Пусть, это будет лишь рисунок на салфетке или пачке "Беломора".
На какие части, требующие графического отображения "чтобы не забыть", вы делите свои программы?
Gudleifr
Gudleifr
Admin

Сообщения : 1095
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор Gudleifr в Вс Сен 03, 2017 11:53 am

Чтобы не быть голословным: простейшие (что понятно из приведенного BASIC-кода) программы, реализованные "современными программистами".

1. Программа, "ЭТО КОТ?", приведенная выше:
Жуть-1:
#include <vector>
#include <string>
#include <iostream>
#include <clocale>
#include <Windows.h>

using namespace std;

std::vector<string> animals;
std::vector<string> animalDiffs;
string firstAnimal = "Кот";

string prompt(const string& sprompt)
{
string a="";
while(a=="")
{
cout << sprompt << "?" << endl;
getline(cin, a);
}

char buf[1023] = {32};
if (a.size() > 1023) a.resize(1023);

OemToCharA(a.c_str(), buf);

return buf;
}

void echo(const string& msg)
{
cout << msg << endl;
}

void getNew()
{
animals.push_back(prompt("А кто это"));
animalDiffs.push_back(prompt("А чем отличается"));
}

bool promtAnimal(const string& animal)
{
string answ = prompt("Это "+animal+"(Д/н)");
if (answ[0] == 'Д' || answ[0] == 'д')
{
echo("Ура!"); return true;
}

return false;
}

bool promptDiff(const string& diff)
{
string answ = prompt("У него есть " + diff + "(Д/н)");
if (answ[0] == 'Д' || answ[0] == 'д') return true;
return false;
}


int main()
{
setlocale(LC_CTYPE, "russian");
bool isFindOrNew;

while (true)
{
echo("Новый раунд!");
echo("Загадай животное...");
 
isFindOrNew = false;

size_t iend = animalDiffs.size();
for (size_t i = 0; i < iend; i++)
{      
if (promptDiff(animalDiffs[i]))
if (promtAnimal(animals[i]))
{
isFindOrNew = true;
break;
}
}
 
  if (!isFindOrNew)
if (!promtAnimal(firstAnimal)) getNew();
 
}
}
Жуть-2:
public class Test {

public static void main(String[] args) throws Exception {
Question q = new ObjectQuestion("Кот");
for (;; ) {
System.out.println("\nЗагадай, животное!");
q = q.ask();
}
}
}

class Prompt {
static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
static String ask(String message) {
System.out.println(message);
try {
return input.readLine();
      } catch (IOException __) {
return "";
}
}
}

abstract class Question {
protected String message;
protected Supplier<Question> yes, no;
public Question ask() {
return (Prompt.ask(message).matches("yes|да") ? yes : no).get();
}
}

class PropertyQuestion extends Question {
public PropertyQuestion(String property, Question q1, Question q2) {
message = "У него есть " + property + "?";
yes = () -> new PropertyQuestion(property, q1.ask(), q2);
no =  () -> new PropertyQuestion(property, q1, q2.ask());
}
}

class ObjectQuestion extends Question {
public ObjectQuestion(String object) {
message = "Это " + object + "?";
yes = () -> {
System.out.println("Угадал!");
return this;
};
no = () -> {
String who = Prompt.ask("А кто это?");
String property = Prompt.ask("Чем отличается?");
return new PropertyQuestion(property, new ObjectQuestion(who), this);
};
}
}

2. Программа, поиска непустых подмножеств, имеющих нулевую сумму, множества из 5 чисел:

10 DATA 2, -7, 4, -1, 1
20 I=5:DIM A(I): P=1:GOSUB 70:N=K2-1
30 FOR J=1 TO N
40 P=2:S=0:GOSUB 70:IF S THEN 60
50 P=3:GOSUB 70:PRINT
60 NEXT J:END
70 K2=1:FOR K=1 TO I:ON P GOTO 90,100,120
80 K2=K2*2:NEXT K:RETURN
90 READ A(K):GOTO 80
100 IF K2 AND J THEN S=S+A(K)
110 GOTO 80
120 IF K2 AND J THEN PRINT K;
130 GOTO 80

Жуть:
// http://ideone.com/H2uNwE
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> out;
void f(int N,int L,const vector<int>&prefix){
auto arr=prefix;
for(auto i=arr.empty()?0:arr.back()+1;i<N;i++){
arr.push_back(i);
if(L==arr.size())out.push_back(arr);
f(N,L,arr);
arr.pop_back();
}
}

int sum(const vector<int>&arr,const vector<int>&ids){int v=0;for(size_t i=0;i<ids.size();i++)v+=arr[ids[i]];return v;}

bool check(const vector<int>&inp){
vector<int> e;
int n=inp.size();
for(int i=0;i<n;i++)f(n,i+1,e);
for(int i=0;i<out.size();i++){
auto&arr=out[i];
if(0==sum(inp,arr)){for(int i=0;i<arr.size();i++)cout<<inp[arr[i]]<<" ";cout<<endl;return true;}
}
return false;
}

int main() {
int inp_arr[]={2,-7,4,8,1}; int n=5;
vector<int> inp(inp_arr,inp_arr+n);
cout<<(check(inp)?"true":"false");
return 0;
}

3. Рисование дерева:

10 RANDOMIZE TIMER
20 DATA 0, 0, .125, .167, .25, .5, 1
30 DIM D(10): FOR I=1 TO 7: READ D(I): NEXT I
40 DEF FNJC=INT(RND*2+3.5)
50 DEF FNJP=RND*.2+.5
60 DEF FNJA=RND*.7
70 DIM X(10),Y(10),DX(10),DY(10)
80 DIM I(10),C(10)
90 W=320:H=200:P=1:X(P)=W/2:Y(P)=H:DX(P)=0:DY(P)=-H/2
100 SCREEN 1,1:CLS
110 C(1)=0:I(1)=0:GOTO 180
120 A=FNJA:IF I(P) AND 1 THEN A=-A
130 DX(P)=(DX(P-1)*COS(A)-DY(P-1)*SIN(A))*2.2/C(P)
140 DY(P)=(DX(P-1)*SIN(A)+DY(P-1)*COS(A))*2.2/C(P)
150 K=(1/C(P))*(FNJP+I(P))
160 X(P)=X(P-1)+DX(P-1)*K
170 Y(P)=Y(P-1)+DY(P-1)*K
180 LINE (X(P),Y(P))-(X(P)+DX(P),Y(P)+DY(P))
190 IF RND>D(P) THEN P=P+1:C(P)=FNJC:I(P)=0:GOTO 120
200 I(P)=I(P)+1:IF I(P)<C(P) THEN 120
210 P=P-1: IF P>1 GOTO 200
220 IF INKEY$="" THEN 220
230 SCREEN 2:CLS
240 SCREEN 0:CLS

Жуть:
program TreeGen;

{$APPTYPE CONSOLE}

{$R *.res}

uses
SysUtils, Graphics, Math;

type
TRndRange = record
minVal, maxVal : Single;
function Rnd(): Single;
end;

TGenParams = record
JointCount : TRndRange;
JointPos   : TRndRange;
JointAngle : TRndRange;
Deep : TRndRange;
end;

TVec2 = record
x, y: Single;
function Rotate(const Angle : Single): TVec2;
class operator Add(const V1, V2 : TVec2): TVec2;
class operator Subtract(const V1, V2 : TVec2): TVec2;
class operator Multiply(const V1: TVec2; const s: Single): TVec2;
end;

function Range(minV, maxV: Single): TRndRange;
begin
Result.minVal := minV;
Result.maxVal := maxV;
end;

{ TRndRange }

function TRndRange.Rnd(): Single;
begin
Result := Random()*(maxVal - minVal) + minVal;
end;

{ TVec2 }

class operator TVec2.Add(const V1, V2: TVec2): TVec2;
begin
Result.x := V1.x + V2.x;
Result.y := V1.y + V2.y;
end;

class operator TVec2.Multiply(const V1: TVec2; const s: Single): TVec2;
begin
Result.x := V1.x * s;
Result.y := V1.y * s;
end;

function TVec2.Rotate(const Angle: Single): TVec2;
Var
s, c : Extended;
begin
SinCos(angle, s, c);
Result.x := x * c - y * s;
Result.y := x * s + y * c;
end;

class operator TVec2.Subtract(const V1, V2: TVec2): TVec2;
begin
Result.x := V1.x - V2.x;
Result.y := V1.y - V2.y;
end;

function Lerp(const V1, V2: TVec2; const k: Single): TVec2;
begin
Result := V1*k + V2*(1.0-k);
end;


procedure DrawLine(const bmp: TBitmap; const StartPt, EndPt: TVec2);
begin
bmp.Canvas.MoveTo(Round(StartPt.x), Round(StartPt.y));
bmp.Canvas.LineTo(Round(EndPt.x), Round(EndPt.y));
end;

procedure DrawBranch(const bmp: TBitmap; const StartPt, Dir: TVec2; GenParams : TGenParams);
var NewParams : TGenParams;
NewStart, NewDir, JointStep: TVec2;
Cnt : Integer;
I: Integer;
angle, k: Single;
begin
NewParams := GenParams;
NewParams.Deep.minVal := Max(0, NewParams.Deep.minVal - 1);
NewParams.Deep.maxVal := Max(0, NewParams.Deep.maxVal - 1);
DrawLine(bmp, StartPt, StartPt + Dir);

if GenParams.Deep.Rnd < 0.5 then Exit;

Cnt := Round(GenParams.JointCount.Rnd);
for I := 0 to Cnt-1 do
begin
angle := GenParams.JointAngle.Rnd;
if I mod 2 = 1 then angle := -angle;
NewDir := Dir.Rotate(angle)*(2.2/Cnt);
k := (1/Cnt)*(GenParams.JointPos.Rnd+I);
NewStart := StartPt + Dir * k;
DrawBranch(bmp, NewStart, NewDir, NewParams);
end;
end;

procedure DrawTree(const bmp: TBitmap; Const GenParams : TGenParams);
var Start, Dir: TVec2;
begin
Start.x := bmp.Width*0.5;
Start.y := bmp.Height;
Dir.x := 0;
Dir.y := -bmp.Height*0.5;
DrawBranch(bmp, Start, Dir, GenParams);
end;

procedure DoWork;
var GenParams: TGenParams;
bmp: TBitmap;
begin
bmp := TBitmap.Create;
try
bmp.Width := 1024;
bmp.Height := 768;
bmp.PixelFormat := pf24bit;

GenParams.JointCount := Range(3, 5);
GenParams.JointPos := Range(0.5, 0.7);
GenParams.JointAngle := Range(0.0, 0.7);
GenParams.Deep := Range(3, 7);

DrawTree(bmp, GenParams);

bmp.SaveToFile('outtree.bmp');
finally
FreeAndNil(bmp);
end;
end;

begin
try
Randomize;
DoWork;
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
end.

P.S. Т.е. мы здесь видим программирование путем подстановки приблизительно подходящие места приблизительно подходящих парадигм. Благодаря этому, вместо использования выразительности современных языков по назначению, получается обфускация - сокрытие ошибок за "общепринятым мусором".
Gudleifr
Gudleifr
Admin

Сообщения : 1095
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор Gudleifr в Сб Июл 07, 2018 12:48 pm

На задачку про скачивание журнала получил забавный ответ:

a. Определим над строками операцию "инкремент". Операция инкремент по определению переводит строку содержащую имя страницы в строку содержащее имя следующей страницы.
Теперь "Дыра между именами X и Y" можно записать (в нормальной форме) как "Y получается из Х после N операций инкремента. N конечно и больше 1".
б. Существование, вычислимость и однозначность операции инкремента. Например, если имена содержат некий хеш, то операция инкремента перестает быть вычислимой и выражение "а" в таком виде теряет смысл.

Т.е. "решающий" полностью проигнорировал начало задачи: "Допустим, я скачиваю из Сети журналы, постранично",- явно указывающее на практическую сторону задачи и полез в абстракции, в которых и начал допускать ошибки.
1) он не учел, что для того, чтобы задача была осмысленной необходимо взаимнооднозначное соответствие номеров файлов и их позициями в списке (что явно указано в условии).
2) если мы вводим понятие "инкремента", то очевидно, стоит ввести и понятие "нуля", "единицы" и "девятки", которые позволят дорешать задачу.
3) очевидно, что для индикации "дыры" достаточно просто заметить неуспех "инкремента", а не искать нужное число инкрементов.
4) в случае невыполнения условия (1) решение задачи упрощается, т.к. придется писать программу нумерации файлов по каталогу (например по той HTML-странице с которой мы производили закачку), которая даст нам номера в любой удобной форме.
5) т.о. единственным важным параметром имен файлов является наличие явного разграничителя между номером страницы и номером журнала, которое может повлиять на логику программы.
Gudleifr
Gudleifr
Admin

Сообщения : 1095
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор kipar в Пн Июл 09, 2018 12:58 pm

По пунктам:
1. Например, пусть имена такие:
journal1-12-abhd5f5
journal1-13-cef4f5d1
journal1-15-583ghab
т.е. включают в себя хеш или скажем названия статей. Мы все еще можем определить дыру и соответствие странице, но не можем по номеру страницы определить имя файла.
Все будет еще сложнее если служебная информация идет раньше номера страницы:
journal1-section1-12
journal1-section1-13
journal1-section1andsection2-15
Это вполне соответствует условию.

2. Страницы могут нумероваться, например, римскими цифрами. Или двумя последовательными страницами (разворотом):
journal1-11-12
journal1-13-14
так что понятия нуля и девятки тут ни к чему, понятие инкремента охватывает все частные случаи.
3. В случае неуспеха инкремента это или начался другой журнал, или дыра. Одно от другого отличается как раз возможностью N инкрементов.
4. страница вполне может быть уже недоступна. В некоторах случаях описанных в (1) дыры найти все еще можно, просто усложним алгоритм, в других - нужна дополнительная информация.
5. Только в частном случае, а условие было про общий случай. Мое решение относится к общему случаю, для того чтобы применить к частному надо всего лишь определить операцию инкремента.

kipar

Сообщения : 2
Дата регистрации : 2018-07-09

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор kipar в Пн Июл 09, 2018 5:48 pm

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

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

kipar

Сообщения : 2
Дата регистрации : 2018-07-09

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор Gudleifr в Вт Июл 10, 2018 8:03 am

Я все-таки укажу на те две ошибки, для излечения от которых я предложил эту задачу, и которые этим диалогом проиллюстрированы.
1) Первая ошибка состоит в двух крайностях "современного программиста": он мыслит только в пределах шаблонов/парадигм (порой замечательно остроумно), при выходе за пределы которых, впадает в панику: "задача неправильная". А ведь "правильных" задач в программировании очень мало.
2) Вторая ошибка - неумение находить закономерности в данных (это мы видели и в задаче про кота, и в задаче про дерево). "Современный программист" выучил типы данных, но не понимает их внутреннего логического устройства.

Как это лечить? Первое - решением математических головоломок. Второе - чтением учебников по программированию на машинных языках (тот же 1-й том "Искусства программирования" Кнута).
Gudleifr
Gudleifr
Admin

Сообщения : 1095
Дата регистрации : 2017-03-29

Вернуться к началу Перейти вниз

Задачки 1 и 2 Empty Re: Задачки 1 и 2

Сообщение автор Спонсируемый контент


Спонсируемый контент


Вернуться к началу Перейти вниз

Вернуться к началу


 
Права доступа к этому форуму:
Вы не можете отвечать на сообщения