2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13  След.
 
 Re: Программирование для неудачников
Сообщение02.03.2013, 20:41 
Аватара пользователя
ya2500 в сообщении #690294 писал(а):
я правильно понимаю, что в "заданном алгебраическом выражении" могут быть использованы только четыре арифметических действия, буквы и скобки? если нет, то- что ещё?
Да.

 
 
 
 Re: Программирование для неудачников
Сообщение02.03.2013, 20:51 
ya2500 в сообщении #690294 писал(а):
огромное спасибо! я тоже попробую поучиться))

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

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

arseniiv в сообщении #690157 писал(а):
получается $O(n\log n)$. Можно лучше?

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

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

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

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

 
 
 
 Re: Программирование для неудачников
Сообщение02.03.2013, 21:28 
Аватара пользователя
ewert в сообщении #690307 писал(а):
Только имейте в виду, что на том сайте задачки далеко не столь тупы, как может показаться на первый взгляд. Вот в случае с инверсиями тупой перебор пар приведёт, скорее всего, к превышению лимита времени (одна секунда). В задачке с корнями уравнения при тупом подходе мы столкнёмся с переполнениями. Остальные не смотрел, но наверняка и там какие-нибудь мины заложены.

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

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

 
 
 
 Re: Программирование для неудачников
Сообщение02.03.2013, 22:00 
я собираюсь получать ввод из файла и выдавать вывод в файл.
и тут же столкнулся с проблемой передачи имени файла в качестве параметра.
вот, простая программа на 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.

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 01:31 
Munin в сообщении #690001 писал(а):
Ханойские башни http://atpp.vstu.edu.ru/cgi-bin/arh_pro ... id_prb=873 (интересно, существует ли простое нерекурсивное решение)

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

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 06:18 
Munin в сообщении #690328 писал(а):
Если в ближайшее время никаких шевелений не будет, я приду к выводу, что никакого желания программировать и не было, а было простое кокетничание.

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

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

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 17:28 
так, с мелкими проблемами при освоении VC++ вроде удалось разобраться..

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


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

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

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

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

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

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

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

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

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

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

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

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

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 18:27 
ya2500 в сообщении #690667 писал(а):
и, ещё- как тут прятать под спойлер?
Тут оффтоп одновременно является спойлером, и текст «Оффтоп» можно поменять на свой, написав так: [​off​=​"Test text."​]ABCDEF[​/​off​]. Получится такое:

(Test text.)

ABCDEF

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

(Оффтоп)

fedcba

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 18:50 
Аватара пользователя
ya2500
Какая жалость, что пока вы придумываете алгоритмы, автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!

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

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

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 21:04 
Zealint в сообщении #690687 писал(а):
У Вас не описание алгоритма, а набор слов, не очень аккуратно между собой связанных.
ну, я нигде этому не учился и в олимпиадах не участвовал. вот, хочу разбирать интересные задачки на форуме и получать отзывы о том, насколько хорошо это у меня получается. спасибо за содействие!

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

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

Munin в сообщении #690712 писал(а):
ya2500
Какая жалость, что пока вы придумываете алгоритмы, автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!
даже не знаю, что и ответить. надеюсь, она ещё появится.

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 22:34 
Аватара пользователя
Munin в сообщении #690712 писал(а):
...автор темы Ktina, неоднократно заявлявшая, что она придумывает алгоритмы неплохо, вместо этого пинает балду и молчит как рыба!

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

 
 
 
 Re: Программирование для неудачников
Сообщение03.03.2013, 23:54 
Аватара пользователя
Ktina в сообщении #690823 писал(а):
Просто я ещё раз наступила на те же самые грабли.
На которые? Все еще вот это:
Ktina в сообщении #683827 писал(а):
"я придумала алгоритм, но не могу реализовать его на $C$"


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

(Оффтоп)

Munin в сообщении #690328 писал(а):
было простое кокетничание
Учитывая поднимаемые ей(им) темы - больше даже похоже на троллинг.

 
 
 
 Re: Программирование для неудачников
Сообщение04.03.2013, 08:52 
Zealint в сообщении #690427 писал(а):
Приходит человек так 250. Даётся первое домашнее задание: задача по уровню типа сложения двух чисел. Получаем сразу минус 150 человек. Потом второе ДЗ, ещё минус 50.


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

 
 
 
 Re: Программирование для неудачников
Сообщение04.03.2013, 09:05 
Esp_ в сообщении #690923 писал(а):
А можете оценить, сколько среди них разбирается в математике и могли бы придумать алгоритмы?

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

 
 
 [ Сообщений: 193 ]  На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group