Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.96
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 01:53     Алгоритмы. Поиск верного решения задачи. #1
Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них:
Культин_С_С++_в задачах и примерах
Рацеев С.М. Язык Си. Структуры данных и алгоритмы
Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.)

Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения.
Расскажите, что вам помогло сложить это самое рациональное решение.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.08.2011, 01:53     Алгоритмы. Поиск верного решения задачи.
Посмотрите здесь:

C++ Две задачи, алгоритмы.
Разработать алгоритмы решения двух задач C++
C++ Алгоритм решения задачи
Задачи на циклические алгоритмы C++
Проблемы с алгоритмом решения задачи C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 12:26     Алгоритмы. Поиск верного решения задачи. #21
Цитата Сообщение от diagon Посмотреть сообщение
Он прямо в посте, который вы процитировали =)

Добавлено через 1 минуту

Да ну, там одна проверка всего...
C++
1
#define abs(x) ( (x) < 0 ? -(x) : (x) )
У меня не отображается...
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 12:28     Алгоритмы. Поиск верного решения задачи. #22
http://********/?main=tasks
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 12:28     Алгоритмы. Поиск верного решения задачи. #23
Цитата Сообщение от diagon Посмотреть сообщение
Да ну, там одна проверка всего...
C++
1
#define abs(x) ( (x) < 0 ? -(x) : (x) )
Так эта одна проверка для каждой цифры - в результате много проверок (количество итерация), я об этом
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 12:29  [ТС]     Алгоритмы. Поиск верного решения задачи. #24
Цитата Сообщение от Olga_ Посмотреть сообщение
Могу поделиться, куда вам скинуть?
нет, книга вся.. решено далеко не все.
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 12:57     Алгоритмы. Поиск верного решения задачи. #25
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
нет, книга вся.. решено далеко не все.
Тогда ладно, а то в книге 5 частей и физически она разбита на две, в первой 1-4 части, во второй 5 часть

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

Добавлено через 18 минут
IIIa66uMEM6eP, а не хотите написать функцию, которая бы возвращала максимальную цифру в восьмеричной записи числа n
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 17:07  [ТС]     Алгоритмы. Поиск верного решения задачи. #26
Цитата Сообщение от Olga_ Посмотреть сообщение
а не хотите написать функцию
попробуем)
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 18:32     Алгоритмы. Поиск верного решения задачи. #27
Сравните потом свой алгоритм с таким:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <cmath>
using namespace std;
 
int Max(unsigned int x)
{
   int max, digit;
   max = x & 7;
   x >>= 3;
   while (x)
   {
       digit = x & 7;
       if (digit > max)
          max = digit;
       x >>= 3;
   }
   return max;
}
 
int main()
{
   int x;
   cout << "x = ";
   cin >> x;
   cout << Max(abs(x)) << endl;
   return 0;
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 18:44     Алгоритмы. Поиск верного решения задачи. #28
Цитата Сообщение от Olga_ Посмотреть сообщение
функцию, которая бы возвращала максимальную цифру в восьмеричной записи числа n
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);
}
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 18:53     Алгоритмы. Поиск верного решения задачи. #29
Цитата Сообщение от 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
Да еще и итеративный алгоритм предпочтительнее рекурсивного
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
06.08.2011, 19:00     Алгоритмы. Поиск верного решения задачи. #30
Цитата Сообщение от Olga_ Посмотреть сообщение
/ и % ой как не экономно, не зря же основание 8
В принципе верно, но если заглянуть в ассемблерный код, то там запросто можно обнаружить сдвиг вместо деления и and вместо остатка.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 19:04     Алгоритмы. Поиск верного решения задачи. #31
Цитата Сообщение от Olga_ Посмотреть сообщение
/ и % ой как не экономно, не зря же основание 8
Да еще и итеративный алгоритм предпочтительнее рекурсивного
Однако мой вариант лучше, ибо красота - страшная сила =)
Ну и надо очень постараться, чтобы подобрать тесты, при которых будет заметна разница.
Могу в свою очередь предложить небольшую задачку: нужно посчитать суммарное количество счастливых билетов с асимптотикой хотя бы O(10^3). Впринципе можно и за O(~140) сделать, но это уже сложнее =)
P.S. счастливый билет - это шестизначное число, сумма левых трех цифр которого равна сумме правых трех цифр.
Сыроежка
Заблокирован
06.08.2011, 20:14     Алгоритмы. Поиск верного решения задачи. #32
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них:
Культин_С_С++_в задачах и примерах
Рацеев С.М. Язык Си. Структуры данных и алгоритмы
Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.)

Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения.
Расскажите, что вам помогло сложить это самое рациональное решение.
Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга!
Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб".
Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element.
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 20:29  [ТС]     Алгоритмы. Поиск верного решения задачи. #33
Цитата Сообщение от Сыроежка Посмотреть сообщение
Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга!
Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб".
Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element.
Решение для задачи давно найдено. По сейджевику уже отписывался.
Сыроежка
Заблокирован
06.08.2011, 20:33     Алгоритмы. Поиск верного решения задачи. #34
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
Решение для задачи давно найдено. По сейджевику уже отписывался.
Вопрос состоял не в том, чтобы найти решение, так как автор темы сразу же указал, что он сделал эту задачу "в лоб" . А вопрос состоял в том, как связать эту задачу со стандартными алгоритмами.
IIIa66uMEM6eP
заставил Бендера
 Аватар для IIIa66uMEM6eP
432 / 288 / 10
Регистрация: 05.12.2010
Сообщений: 1,642
Записей в блоге: 6
06.08.2011, 20:39  [ТС]     Алгоритмы. Поиск верного решения задачи. #35
Цитата Сообщение от Сыроежка Посмотреть сообщение
А вопрос состоял в том, как связать эту задачу со стандартными алгоритмами.
вы меня не поняли.. вопрос был как научится алгоритмически мыслить, на что были даны очень хорошие ответы.
Сыроежка
Заблокирован
06.08.2011, 20:41     Алгоритмы. Поиск верного решения задачи. #36
Цитата Сообщение от IIIa66uMEM6eP Посмотреть сообщение
вы меня не поняли.. вопрос был как научится алгоритмически мыслить, на что были даны очень хорошие ответы.
А чем мой ответ плох?! Я вам подсказал очень оригинальную идею, которая никому в голову даже не пришла! Как раз чтобы алгоритмически мыслить, нужно хорошо знать стандартные алгоритмы.

Я так понимаю, что вы просто не в состоянии оценить мою идею! Значит мало книг вы еще прочитали по С++!
Olga_
 Аватар для Olga_
840 / 182 / 16
Регистрация: 01.08.2011
Сообщений: 502
06.08.2011, 20:58     Алгоритмы. Поиск верного решения задачи. #37
Цитата Сообщение от diagon Посмотреть сообщение
Однако мой вариант лучше...
Что за самовлюбленный народ..., каждый третий на этом форуме... аж желания общаться нет и посещать этот форум...
Сыроежка
Заблокирован
06.08.2011, 21:09     Алгоритмы. Поиск верного решения задачи. #38
Чтобы вы поняли, насколько я подсказал интересную идею, то написание предложенного мною итератора повзолит вам использовать его в любоых стандартных алгоритмах! Вы можете, например, не только найти максимальную цифру числа, но и минимальную. Вы можете также вывести число в обратном порядке. Вы можете проверить, существует ли в числе конкретная цифра и т.д. То есть перспективы у такого подхода неограничены в отличии от всех тех алгоритмов, которые вам здесь приводили, так как эти алгоритмы решают всего лишь одну задачу, а потому совершенно не гибкие и имеют очень узкое применение!
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.08.2011, 21:42     Алгоритмы. Поиск верного решения задачи. #39
Цитата Сообщение от Olga_ Посмотреть сообщение
Что за самовлюбленный народ
Что за серьезное отношение к юмору, пусть и плоскому?

Цитата Сообщение от Сыроежка Посмотреть сообщение
То есть перспективы у такого подхода неограничены в отличии от всех тех алгоритмов, которые вам здесь приводили, так как эти алгоритмы решают всего лишь одну задачу, а потому совершенно не гибкие и имеют очень узкое применение!
Быстрее за минуту-другую написать нужную функцию, чем разбираться в документации неизвестного как реализованного алгоритма.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2011, 21:45     Алгоритмы. Поиск верного решения задачи.
Еще ссылки по теме:

C++ Разработать алгоритмы и программы решения задач
Нужны задачи для их решения C++
C++ не знаю решения задачи в c ++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Сыроежка
Заблокирован
06.08.2011, 21:45     Алгоритмы. Поиск верного решения задачи. #40
Цитата Сообщение от diagon Посмотреть сообщение
Что за серьезное отношение к юмору, пусть и плоскому?


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

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

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

Вы - тот программист, который вместо того, чтобы, допустим, лжин раз написать реверсивный итератор, постоянно пишет новую функцию для решения задачи, которая делается за минуту с помощью реверсивных итераторв!
Yandex
Объявления
06.08.2011, 21:45     Алгоритмы. Поиск верного решения задачи.
Ответ Создать тему
Опции темы

Текущее время: 00:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru