Задачки 1 и 2

Перейти вниз

Задачки 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 раз(а)
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

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

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

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

Посмотреть профиль

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

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. Т.е. мы здесь видим программирование путем подстановки приблизительно подходящие места приблизительно подходящих парадигм. Благодаря этому, вместо использования выразительности современных языков по назначению, получается обфускация - сокрытие ошибок за "общепринятым мусором".
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

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

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

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

Посмотреть профиль

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

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

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 2:53 pm

kipar пишет:По пунктам:
1. Например, пусть имена такие:
journal1-12-abhd5f5
...
Это легко. И вполне попадает под общее решение.

kipar пишет:journal1-section1andsection2-15

Это не попадает под условие задачи (имена в списке директория идут по порядку), но легко решается.

kipar пишет:так что понятия нуля и девятки тут ни к чему, понятие инкремента охватывает все частные случаи.
"Икремент" - это лишь очевидный путь решения, а "ноль" и "девятка" - дают решение. Римские числа не удовлетворяют условию задачи.

kipar пишет:Одно от другого отличается как раз возможностью N инкрементов.
Это избыточно и по условию задачи, и по сути практической проблемы.

kipar пишет:страница вполне может быть уже недоступна.
Если для извлечения номеров придется открывать документы (очевидный случай (1)  не рассматпиваем), то это очевидно, уже другая задача.

kipar пишет:Только в частном случае, а условие было про общий случай.
См. условие задачи.

kipar пишет:Мое решение относится к общему случаю
Решения Вами представлено не было. Вы лишь перефразировали условие задачи. И слегка его переврали.


Последний раз редактировалось: Gudleifr (Пн Июл 09, 2018 3:13 pm), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

Gudleifr пишет:Это легко. И вполне попадает под общее решение.
но при этом однозначного соответствия уже нет. Мы не можем по номеру страницы "14" определить какой файл ей должен соответствовать, можем только убедиться что этого файла нет.

Gudleifr пишет:Это не попадает под условие задачи (имена в списке директрория), но легко решается.
Попадает. В условии не сказано что порядок сортировки в директории должен совпадать с сортировкой по номерам страниц.
Он может не совпадать и в более простом случае:
journal1-8
journal1-9
journal1-10

Gudleifr пишет:Римские числа не удовлетворяют условию задачи.
Удовлетворяют. И если с римскими цифрами еще можно поспорить (кто в здравом уме будет использовать их для нумерации страниц), то нумерацию разворотов я лично видел когда качал.

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

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

kipar

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 3:23 pm

kipar пишет:Мы не можем по номеру страницы "14" определить какой файл ей должен соответствовать
В задаче этого не требовалось.

kipar пишет:[Римские числа] Удовлетворяют.
Пардон, мне показалось, что "подряд" в условии задачи очевидно. Моя вина. Нумерация парами условия задачи не меняет и решения не усложняет.

kipar пишет:Все также есть папка забитая файлами, dir выдающий имена файлов и требование к программе находить дыры. Нигде в условии не сказано, что программа не может открывать файлы.
Именно. Не может. Поэтому это и другая задача.

kipar пишет:Вообще изначально я хотел своим ответом показать, что формулировка условия задачи настолько расплывчата...
Что не мешает ее решить, предложив достаточно подробный алгоритм.
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

> В задаче этого не требовалось.
не требовалось. Я говорю про взаимнооднозначное соответствие, которого в этом случае нет.

> Именно. Не может. Поэтому это и другая задача.
Повторюсь, в условии не запрещено открывать файлы. Поэтому это та же задача.

> Что не мешает ее решить, предложив достаточно подробный алгоритм.
из-за расплывчатого условия на любой алгоритм можно будет придумать контрпример. Т.к. формат имен неизвестен, то и римские цифры и шестнадцатеричные и все приведенные мной выше варианты вполне допустимы - а что, кто может гарантировать что файлы не будут названы именно так. Разумеется, после каждого контрпримера можно доработать алгоритм чтобы учесть его, но это малоперспективное занятие. Остатется только предлагать по возможности обобщенное решение, под которое бы подходил любой контрпример. Под мою идею с "инкрементом" подходят и римские цифры и даже чтение из файла, правда она ломается на случае с хешем. Разумеется, конкретного решения она не дает, для решения нужно узнать подробности об именах файлов и сформулировать операцию "инкремент", но это самое общее что пришло в голову. Под вашу идею с "наличием явного разграничителя между номером страницы и номером журнала" найти контрпример еще проще. Например разграничитель может меняться от журнала к журналу, присутствовать для одних и отсутствовать для других. Или номер страницы может идти до имени журнала.

kipar

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 4:10 pm

kipar пишет:...
Повторю: "Допустим, я скачиваю из Сети журналы, постранично".
Очевидно, что жуткие "котрпримеры", которые Вы собираетесь придумывать, заставят меня скачивать как-то иначе (скорее всего, тупо сохраняя под нужным номеров, вручную или используя каталог). Никто не будет искать следующий номер средствами изощренной криптографии.
И повторю, т.к. "дыра" очевидно и означает "сбой инкремента", то решение "возьмем его и посмотрим", решением не является.
Как не является идеей и "наличие разграничителя", ведь наличие "номера журнала" и "номера страницы" вполне очевидно из условия.
Вы правы, решение может немного плавать, однако оно есть, а Вы так к нему и не приблизились.

avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

Очевидно, что жуткие "котрпримеры", которые Вы собираетесь придумывать, заставят меня скачивать как-то иначе (скорее всего, тупо сохраняя под нужным номеров, вручную или используя каталог)
Отнюдь не очевидно. Для каждого порог когда он испугается сложности имен и начнет скачивать под другим именем вместо того чтоб парсить разный, к тому же зависит от объема данных. На римских цифрах я бы, наверное, призадумался, но такая ерунда как номер страницы идущий до а не после названия журнала и начинающийся с 1 а не с 001 меня бы точно не испугала. Ну а при достаточно большом объеме я бы не и посмотреть как можно выковырять номер из пдф-файла не поленился.

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

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

kipar

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 4:34 pm

kipar пишет:...
Вас кидает из стороны в сторону. То Вы заявляете о трудностях, которые на решение практически не влияют (те же римские числа, или нетривиальное расположение номера/имени), то, наоборот, начинаете излишне усложнять задачу (открывать pdf-ы). Начинайте же решать!
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

Как пример, ранее вы утверждали что римские цифры или другое расположение номера условиям задачи не удовлетворяют.

kipar

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

Посмотреть профиль

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

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

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

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

kipar пишет:Как пример, ранее вы утверждали что римские цифры или другое расположение номера условиям задачи не удовлетворяют.
Писал. Не удовлетворяют. Но на общее решение практически не влияют.
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

> Впрочем, если Вы действительно откроете папку такого вида, Вы возможно увидите и решение.

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

kipar

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

Посмотреть профиль

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

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

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

kipar пишет:остается только гадать есть там римские цифры или нет, никаких решений предлагать нет смысла.
Зачем гадать, если в условии написано, что нет.


Последний раз редактировалось: Gudleifr (Вт Июл 10, 2018 8:02 am), всего редактировалось 1 раз(а)
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

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

kipar

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 6:23 pm

kipar пишет:Ничего подобного там не написано. Там написано, что dir выдает список
Там написано: "Все просто: dir или ls выдают имена файлов подряд". Правильнее, конечно было бы "по порядку", но за это я уже извинялся. Думаю, для любого человека слова "журналы лежат подряд" несут очевидный смыл упорядочения.

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

kipar пишет:Та же проблема, что и и в остальных ваших "задачках" - половина данных не написана т.к. кажется вам очевидными
Что поделать, мы тут занимаемся программированием, а не копипастой готовых решений. Попробуйте для каждого Вашего контрпримера выяснить, что конкретно оно должно менять в решении. Допустим, как Вы выше предложили Вам придется "открывать pdf". Окажет ли это влияние на программу поиска дыр? Нет, конечно. Нам придется перебрать все pdf-ы, и для каждого получить номер. Этот номер мы занесем в список или соответствующим образом переименуем файлы. (В силу условия задачи порядок при этом не нарушится, но кто мешает отсортировать список программой sort?) После этого мы запускаем программу поиска дыр, скармливая ей наш список или результат dir. И что поменялось в решении? Ничего.
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

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

kipar

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

Посмотреть профиль

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

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

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

kipar пишет:значит только что они лежат без пропусков.
Т.е. верхние не висят в воздухе над нижними? Странно, да.

kipar пишет:Пока нет возражений?
Разумеется, есть. Это не имеет отношения к исходной задаче.

kipar пишет:Для любого конкретного решения можно найти контрпример под который решение придется менять.
Включая привлечение Кота Шредингера и Большую Теорему Ферма? Можно. Подскажу еще раз. Найдите простейшее решение. Найдите контрпример. Посмотрите, что меняется в решении. Можно ли обобщить? Пройдите несколько итераций. Посмотрите, есть ли этих решениях что-то общее (окромя "инкремента").
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

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

kipar пишет:Подскажу еще раз. Найдите простейшее решение. Найдите контрпример. Посмотрите, что меняется в решении. Можно ли обобщить? Пройдите несколько итераций. Посмотрите, есть ли этих решениях что-то общее (окромя "инкремента").
Даже "инкремент" не решает задачу в общем виде. Ну да, можно в контрпримерах и до теоремы Ферма с котом дойти, решение будет становиться еще более абстрактным.
К практике это не имеет отношения т.к. на практике после пары итераций исходный каталог обработается и последующие обобщения будут излишними.

kipar

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

Посмотреть профиль

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

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

Сообщение автор Gudleifr в Пн Июл 09, 2018 7:25 pm

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

kipar пишет:В таком случае, жду нормальной формулировки (хотя бы с пояснением насчет упорядоченности), без нее обсуждать нечего.
Это излишне.
avatar
Gudleifr
Admin

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

Посмотреть профиль

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

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

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

ок, излишне так и излишне.

kipar

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

Посмотреть профиль

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

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

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

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

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

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

Посмотреть профиль

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

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

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


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


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

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


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