Программирование для неудачников

[Xaositect]

ya2500 в сообщении #690294 писал(а):

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

Да.

[ewert]

ya2500 в сообщении #690294 писал(а):

огромное спасибо! я тоже попробую поучиться))

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

-- Сб мар 02, 2013 22:06:30 --

arseniiv в сообщении #690157 писал(а):

получается $O(n\log n)$. Можно лучше?

Вряд ли -- в конце-то концов, это задача типа сортировки. Но и этого хватило бы.

Только вот я не очень понял, как Вы собираетесь вставлять элемент в массив за логарифм объёма входных данных. Определить позицию вставки -- куда ни шло, но потом ведь массив надо ещё и раздвинуть, что начисто сжирает весь логарифм.

Ну и (так, в порядке придирки) -- приведите в чувство сумму.

А, да, ещё забыл. Вводить входной массив нужно, наверное, всё-таки сразу. А то за наносекунды ввести очередное число вряд ли выйдет.

[Munin]

ewert в сообщении #690307 писал(а):

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

Ну, от Ktina услышать бы хотя бы самые примитивные решения, не учитывающие таких "мин"...

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

[ya2500]

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

Используется синтаксис C++

// Maze_Path.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"


int _tmain(int argc, _TCHAR* argv[])
{
        if(argc==2) // если программу запустили с одним параметром
        {
                FILE *file;
                char* file_name = argv[1]; // получаем название файла
                char load_string[50] = "none"; // что запишем в файл

                file = fopen(file_name, "w"); // открываем файл для записи
                // w- write, r- read, a- append

                fputs(load_string, file); // помещаем строку в файл
                // fputc, fputs, fgetc, fgets, fprintf, fscanf
        }

        return 0;
}
 

потому что массив аргументов имеет тип _THCAR. как этот тип преобразовать, чтобы я мог передать аргумент в функцию fopen?

-- 02.03.2013, 23:03 --

я раньше программировал на Delphi, и вот, пытаюсь освоить VC++ 2008.

[lim(f(x))]

Munin в сообщении #690001 писал(а):

Ханойские башни http://atpp.vstu.edu.ru/cgi-bin/arh_pro ... id_prb=873 (интересно, существует ли простое нерекурсивное решение)

В начале "Конкретной математики" Кнута рассматривается задача на нахождение числа перекладываний (всего), он показывает, что формула для $n$ дисков $2^n - 1$.
Подсчёт определённых перекладываний не встречал.

[Zealint]

Munin в сообщении #690328 писал(а):

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

Это, кстати, обычное дело. У нас обычно в начале сезона много желающих добиться высоких результатов, школьники так или иначе наслышаны о разных соревнованиях и об успехах как на Российском, так и на международном уровне. Приходит человек так 250. Даётся первое домашнее задание: задача по уровню типа сложения двух чисел. Получаем сразу минус 150 человек. Потом второе ДЗ, ещё минус 50. Так, в конце года остаётся как раз одна-две команды по 3 человека. А остальные уходят в недоумении "о, так тут ещё и думать надо что ли? А я думал только кнопки нажимать - и уже завтра напишу свою супер-стратегическую игру".

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

[ya2500]

так, с мелкими проблемами при освоении VC++ вроде удалось разобраться..

теперь вопрос по алгоритмам: выбрал я, для начала, самую простую из увиденных здесь задач:

Munin в сообщении #690001 писал(а):

Путь в лабиринте http://atpp.vstu.edu.ru/cgi-bin/arh_pro ... id_prb=246

путь в лабиринте можно искать по-разному, но в задаче требуют именно кратчайший => я прихожу к мысли, что такая задача оставляет только один способ реализации:
- отмечаем поле выхода нулём
- пока не дошли до входа, делаем:
-- сканируем массив, отмечаем неотмеченные поля, соседние с отмеченными, числом на 1 больше, чем минимальное из соседних полей
- таким образом, в отмеченных полях будет храниться расстояние до выхода
- от входа отмечаем знаками '*' путь, двигаясь по пути уменьшения расстояния до выхода
- выводим массив в файл:
-- вместо числовых отметок выводим '.'
-- знаки '#', '.', '*' выводим как есть

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

такой вот алгоритм.

вопрос в том, возможно ли для этой задачи придумать алгоритм лучше?

и, ещё- как тут прятать под спойлер?

[Zealint]

У Вас не описание алгоритма, а набор слов, не очень аккуратно между собой связанных. Например, "от входа отмечаем знаками '*' путь, двигаясь по пути уменьшения расстояния до выхода". Если прочитать это так, как прочитал я, то это неправильно. А что Вы имели ввиду, непонятно. А неправильно (если читать как я) то, что между двумя клетками с числами, отличающимися на 1, может не быть пути, длиной 1 шаг.

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

Поместить начальную клетку в очередь.
Пометить начальную клетку числом 0.
Пока очередь не пуста, повторять:
  - достать очередную клетку i из очереди.
  - всех соседей j клетки i, которые ещё не были в очереди, пометить числом, на единицу большим, чем число в клетке i и затолкать их тоже в очередь.

Ответом будет число в клетке, интерпретируемой как выход.

Это общая идея, кое-что нужно учесть, в зависимости от желаемого результата.
Как вывести при этом маршрут? Нетрудно: когда заталкиваем соседа j клетки i в очередь, отмечаем pi[j]=i, а потом двигаемся по массиву pi от финальной клетки в начальную (в обратном порядке).

А вообще, задача поставлена некорректно.

Цитата:

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

В такой постановке кратчайший путь будет таким: сначала идем до упора вправо, а потом до упора вниз. Ведь не сказано, что нельзя ходить по закрашенным клеткам. Они просто закрашены и всё - какой нам дело?

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

[arseniiv]

ya2500 в сообщении #690667 писал(а):

и, ещё- как тут прятать под спойлер?

Тут оффтоп одновременно является спойлером, и текст «Оффтоп» можно поменять на свой, написав так: [​off​=​"Test text."​]ABCDEF[​/​off​]. Получится такое:

(Test text.)

ABCDEF

А если без параметра, получится такое:

(Оффтоп)

fedcba

[Munin]

ya2500
Какая жалость, что пока вы придумываете алгоритмы, автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!

Zealint в сообщении #690687 писал(а):

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

Не будьте столь строги. Это нормальный задел. Конечно, многое ещё остаётся на уточнение.

[ya2500]

Zealint в сообщении #690687 писал(а):

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

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

Zealint в сообщении #690687 писал(а):

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

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

Zealint в сообщении #690687 писал(а):

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

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

Munin в сообщении #690712 писал(а):

ya2500
Какая жалость, что пока вы придумываете алгоритмы, автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!

даже не знаю, что и ответить. надеюсь, она ещё появится.

[Ktina]

Munin в сообщении #690712 писал(а):

...автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!

Просто я ещё раз наступила на те же самые грабли.

[myhand]

Ktina в сообщении #690823 писал(а):

Просто я ещё раз наступила на те же самые грабли.

На которые? Все еще вот это:

Ktina в сообщении #683827 писал(а):

"я придумала алгоритм, но не могу реализовать его на $C$"

Ну так на человеческом-то языке сумеете изложить алгоритм?

(Оффтоп)

Munin в сообщении #690328 писал(а):

было простое кокетничание

Учитывая поднимаемые ей(им) темы - больше даже похоже на троллинг.

[Esp_]

Zealint в сообщении #690427 писал(а):

Приходит человек так 250. Даётся первое домашнее задание: задача по уровню типа сложения двух чисел. Получаем сразу минус 150 человек. Потом второе ДЗ, ещё минус 50.

А можете оценить, сколько среди них разбирается в математике и могли бы придумать алгоритмы?

[Zealint]

Esp_ в сообщении #690923 писал(а):

А можете оценить, сколько среди них разбирается в математике и могли бы придумать алгоритмы?

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