Алгоритмы. Поиск верного решения задачи.

Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них:
Культин_С_С++_в задачах и примерах
Рацеев С.М. Язык Си. Структуры данных и алгоритмы
Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.)

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

0

Сообщение от diagon Он прямо в посте, который вы процитировали =) Добавлено через 1 минуту Да ну, там одна проверка всего... C++ 1 #define abs(x) ( (x) < 0 ? -(x) : (x) )

У меня не отображается...

0

http://acmp.ru/?main=tasks

1

Сообщение от diagon Да ну, там одна проверка всего... C++ 1 #define abs(x) ( (x) < 0 ? -(x) : (x) )

Так эта одна проверка для каждой цифры - в результате много проверок (количество итерация), я об этом

0

Сообщение от Olga_ Могу поделиться, куда вам скинуть?

нет, книга вся.. решено далеко не все.

0

Сообщение от IIIa66uMEM6eP нет, книга вся.. решено далеко не все.

Тогда ладно, а то в книге 5 частей и физически она разбита на две, в первой 1-4 части, во второй 5 часть

Добавлено через 8 минут
Еще есть неплохая книжка Шень А. Программирование: теоремы и задачи. Она ориентирована на Паскаль, но можно попытаться в С++ попереводить и проанализировать

Добавлено через 18 минут
IIIa66uMEM6eP, а не хотите написать функцию, которая бы возвращала максимальную цифру в восьмеричной записи числа n

0

Сообщение от Olga_ а не хотите написать функцию

попробуем)

0

Сравните потом свой алгоритм с таким:

0

Сообщение от Olga_ функцию, которая бы возвращала максимальную цифру в восьмеричной записи числа n

0

Сообщение от diagon C++ 1 2 3 4 5 6 7 8 9 #include <iostream> int max_digit(int n){     return n ? std::max( max_digit(n / 8), abs(n % 8) ) : 0; } int main(){     int n;     std::cin >> n;     std::cout << max_digit(n); }

/ и % ой как не экономно, не зря же основание 8
Да еще и итеративный алгоритм предпочтительнее рекурсивного

0

Сообщение от Olga_ / и % ой как не экономно, не зря же основание 8

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

1

Сообщение от Olga_ / и % ой как не экономно, не зря же основание 8 Да еще и итеративный алгоритм предпочтительнее рекурсивного

Однако мой вариант лучше, ибо красота - страшная сила =)
Ну и надо очень постараться, чтобы подобрать тесты, при которых будет заметна разница.
Могу в свою очередь предложить небольшую задачку: нужно посчитать суммарное количество счастливых билетов с асимптотикой хотя бы O(10^3). Впринципе можно и за O(~140) сделать, но это уже сложнее =)
P.S. счастливый билет - это шестизначное число, сумма левых трех цифр которого равна сумме правых трех цифр.

1

Сообщение от IIIa66uMEM6eP Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них: Культин_С_С++_в задачах и примерах Рацеев С.М. Язык Си. Структуры данных и алгоритмы Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.) Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения. Расскажите, что вам помогло сложить это самое рациональное решение.

Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга!
Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб".
Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element.

0

Сообщение от Сыроежка Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга! Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб". Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element.

Решение для задачи давно найдено. По сейджевику уже отписывался.

0

Сообщение от IIIa66uMEM6eP Решение для задачи давно найдено. По сейджевику уже отписывался.

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

0

Сообщение от Сыроежка А вопрос состоял в том, как связать эту задачу со стандартными алгоритмами.

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

0

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

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

Я так понимаю, что вы просто не в состоянии оценить мою идею! Значит мало книг вы еще прочитали по С++!

0

Сообщение от diagon Однако мой вариант лучше...

Что за самовлюбленный народ..., каждый третий на этом форуме... аж желания общаться нет и посещать этот форум...

0

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

0

Сообщение от Olga_ Что за самовлюбленный народ

Что за серьезное отношение к юмору, пусть и плоскому?

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

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

0

Сообщение от diagon Что за серьезное отношение к юмору, пусть и плоскому? Быстрее за минуту-другую написать нужную функцию, чем разбираться в документации неизвестного как реализованного алгоритма.

Глупость! Это как раз подход тех, кого нельзя считать программистами. Программирование - это построение абстракций. Как только мало-мальски изменятся условия задачи, вам придется писать очередную " нужную" функцию! А зачем тогда, позвольте вас спросить, разработчики С++ старались и писали стандартные алгоритмы?! Я вам сразу же могу сказать, что с таким мышлением, как у вас, из вас выйдет плохой программист так сказать, "местечковый", который не в состоянии мыслить абстрактно и на каждый "чих" пишет "нужную" функцию!

Представьте к примеру, что условия задачи изменились, и нужно подсчитать сумму цифр числа? Что тогда? Будете писать очередную "нужную" функцию? А если требуется подсчитать число четных цифр в числе? Опять будете писать "Нужную" функцию?!

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

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

0