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

@IIIa66uMEM6eP · Регистрация: 05.12.2010

Author24 — интернет-сервис помощи студентам

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

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

@Olga_ · 06.08.2011, 12:26

Сообщение от diagon

Он прямо в посте, который вы процитировали =)

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

Да ну, там одна проверка всего...

C++

1	#define abs(x) ( (x) < 0 ? -(x) : (x) )

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

@diagon · 06.08.2011, 12:28

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

@Olga_ · 06.08.2011, 12:28

Сообщение от diagon

Да ну, там одна проверка всего...

C++

1	#define abs(x) ( (x) < 0 ? -(x) : (x) )

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

@IIIa66uMEM6eP · 06.08.2011, 12:29 **[ТС]**

Сообщение от Olga_

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

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

@Olga_ · 06.08.2011, 12:57

Сообщение от IIIa66uMEM6eP

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

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

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

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

@IIIa66uMEM6eP · 06.08.2011, 17:07 **[ТС]**

Сообщение от Olga_

а не хотите написать функцию

попробуем)

@Olga_ · 06.08.2011, 18:32

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

C++

#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 · 06.08.2011, 18:44

Сообщение от Olga_

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

C++

#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_ · 06.08.2011, 18:53

Сообщение от diagon

C++

#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 · 06.08.2011, 19:00

Сообщение от Olga_

/ и % ой как не экономно, не зря же основание 8

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

@diagon · 06.08.2011, 19:04

Сообщение от Olga_

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

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

@~~Сыроежка~~ · 06.08.2011, 20:14

Сообщение от IIIa66uMEM6eP

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

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

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

@IIIa66uMEM6eP · 06.08.2011, 20:29 **[ТС]**

Сообщение от Сыроежка

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

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

@~~Сыроежка~~ · 06.08.2011, 20:33

Сообщение от IIIa66uMEM6eP

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

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

@IIIa66uMEM6eP · 06.08.2011, 20:39 **[ТС]**

Сообщение от Сыроежка

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

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

@~~Сыроежка~~ · 06.08.2011, 20:41

Сообщение от IIIa66uMEM6eP

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

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

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

@Olga_ · 06.08.2011, 20:58

Сообщение от diagon

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

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

@~~Сыроежка~~ · 06.08.2011, 21:09

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

@diagon · 06.08.2011, 21:42

Сообщение от Olga_

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

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

Сообщение от Сыроежка

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

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

@~~Сыроежка~~ · 06.08.2011, 21:45

Сообщение от diagon

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

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

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

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

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

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

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	06.08.2011, 12:28	22
	http://acmp.ru/?main=tasks 1

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	06.08.2011, 12:57	25
	Сообщение от IIIa66uMEM6eP нет, книга вся.. решено далеко не все. Тогда ладно, а то в книге 5 частей и физически она разбита на две, в первой 1-4 части, во второй 5 часть Добавлено через 8 минут Еще есть неплохая книжка Шень А. Программирование: теоремы и задачи. Она ориентирована на Паскаль, но можно попытаться в С++ попереводить и проанализировать Добавлено через 18 минут IIIa66uMEM6eP, а не хотите написать функцию, которая бы возвращала максимальную цифру в восьмеричной записи числа n 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	06.08.2011, 19:00	30
	Сообщение от Olga_ / и % ой как не экономно, не зря же основание 8 В принципе верно, но если заглянуть в ассемблерный код, то там запросто можно обнаружить сдвиг вместо деления и and вместо остатка. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	06.08.2011, 19:04	31
	Сообщение от Olga_ / и % ой как не экономно, не зря же основание 8 Да еще и итеративный алгоритм предпочтительнее рекурсивного Однако мой вариант лучше, ибо красота - страшная сила =) Ну и надо очень постараться, чтобы подобрать тесты, при которых будет заметна разница. Могу в свою очередь предложить небольшую задачку: нужно посчитать суммарное количество счастливых билетов с асимптотикой хотя бы O(10^3). Впринципе можно и за O(~140) сделать, но это уже сложнее =) P.S. счастливый билет - это шестизначное число, сумма левых трех цифр которого равна сумме правых трех цифр. 1

@~~Сыроежка~~ Заблокирован
	06.08.2011, 20:33	34
	Сообщение от IIIa66uMEM6eP Решение для задачи давно найдено. По сейджевику уже отписывался. Вопрос состоял не в том, чтобы найти решение, так как автор темы сразу же указал, что он сделал эту задачу "в лоб" . А вопрос состоял в том, как связать эту задачу со стандартными алгоритмами. 0

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,708 Записей в блоге: 6
		1
	Алгоритмы. Поиск верного решения задачи. 06.08.2011, 01:53. Показов 8868. Ответов 79 Метки нет (Все метки) Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них: Культин_С_С++_в задачах и примерах Рацеев С.М. Язык Си. Структуры данных и алгоритмы Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.) Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения. Расскажите, что вам помогло сложить это самое рациональное решение. 0

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,708 Записей в блоге: 6
	06.08.2011, 12:29 [ТС]	24
	Сообщение от Olga_ Могу поделиться, куда вам скинуть? нет, книга вся.. решено далеко не все. 0

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,708 Записей в блоге: 6
	06.08.2011, 17:07 [ТС]	26
	Сообщение от Olga_ а не хотите написать функцию попробуем) 0

@~~Сыроежка~~ Заблокирован
	06.08.2011, 20:14	32
	Сообщение от IIIa66uMEM6eP Крик души. Есть много замечательных книг по программированию, в них часто приводят стандартные алгоритмы. Переработал несколько из них: Культин_С_С++_в задачах и примерах Рацеев С.М. Язык Си. Структуры данных и алгоритмы Седжвик Р. Фундаментальные алгоритмы на C++. (увы не вся.) Но после прочтения, все равно огромные трудности с алгоритмической частью. Курс программирования дался очень тяжко. Подскажите в каком направлении двигаться, литературу честно говоря читать уже в без толку, когда не могу придумать как найти наибольшую цифру в числе. Конечно можно набрать кучу доп.задач, пробовать решать что то с форума.. Как говорил мой преподаватель: "я в программировании был полный ноль, пока не встретил одну книгу которая и научила программировать" - ведь программирование это не знание языка, а способность находить рациональные решения. Расскажите, что вам помогло сложить это самое рациональное решение. Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга! Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб". Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element. 0

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,708 Записей в блоге: 6
	06.08.2011, 20:29 [ТС]	33
	Сообщение от Сыроежка Я поражаюсь тому, что вы осилили Седжвика. Насколько я знаю, это довольно толстая книга! Что касается вашей задачи, то ее легко сделать,как говорится, "в лоб". Но есть более изящное решение, если вас интересуют стандартные алгоритмы. Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element. Решение для задачи давно найдено. По сейджевику уже отписывался. 0

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,708 Записей в блоге: 6
	06.08.2011, 20:39 [ТС]	35
	Сообщение от Сыроежка А вопрос состоял в том, как связать эту задачу со стандартными алгоритмами. вы меня не поняли.. вопрос был как научится алгоритмически мыслить, на что были даны очень хорошие ответы. 0

@~~Сыроежка~~ Заблокирован
	06.08.2011, 20:41	36
	Сообщение от IIIa66uMEM6eP вы меня не поняли.. вопрос был как научится алгоритмически мыслить, на что были даны очень хорошие ответы. А чем мой ответ плох?! Я вам подсказал очень оригинальную идею, которая никому в голову даже не пришла! Как раз чтобы алгоритмически мыслить, нужно хорошо знать стандартные алгоритмы. Я так понимаю, что вы просто не в состоянии оценить мою идею! Значит мало книг вы еще прочитали по С++! 0

@Olga_ 848 / 190 / 18 Регистрация: 01.08.2011 Сообщений: 505
	06.08.2011, 20:58	37
	Сообщение от diagon Однако мой вариант лучше... Что за самовлюбленный народ..., каждый третий на этом форуме... аж желания общаться нет и посещать этот форум... 0

@~~Сыроежка~~ Заблокирован
	06.08.2011, 21:09	38
	Чтобы вы поняли, насколько я подсказал интересную идею, то написание предложенного мною итератора повзолит вам использовать его в любоых стандартных алгоритмах! Вы можете, например, не только найти максимальную цифру числа, но и минимальную. Вы можете также вывести число в обратном порядке. Вы можете проверить, существует ли в числе конкретная цифра и т.д. То есть перспективы у такого подхода неограничены в отличии от всех тех алгоритмов, которые вам здесь приводили, так как эти алгоритмы решают всего лишь одну задачу, а потому совершенно не гибкие и имеют очень узкое применение! 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	06.08.2011, 21:42	39
	Сообщение от Olga_ Что за самовлюбленный народ Что за серьезное отношение к юмору, пусть и плоскому? Сообщение от Сыроежка То есть перспективы у такого подхода неограничены в отличии от всех тех алгоритмов, которые вам здесь приводили, так как эти алгоритмы решают всего лишь одну задачу, а потому совершенно не гибкие и имеют очень узкое применение! Быстрее за минуту-другую написать нужную функцию, чем разбираться в документации неизвестного как реализованного алгоритма. 0

@~~Сыроежка~~ Заблокирован
	06.08.2011, 21:45	40
	Сообщение от diagon Что за серьезное отношение к юмору, пусть и плоскому? Быстрее за минуту-другую написать нужную функцию, чем разбираться в документации неизвестного как реализованного алгоритма. Глупость! Это как раз подход тех, кого нельзя считать программистами. Программирование - это построение абстракций. Как только мало-мальски изменятся условия задачи, вам придется писать очередную " нужную" функцию! А зачем тогда, позвольте вас спросить, разработчики С++ старались и писали стандартные алгоритмы?! Я вам сразу же могу сказать, что с таким мышлением, как у вас, из вас выйдет плохой программист так сказать, "местечковый", который не в состоянии мыслить абстрактно и на каждый "чих" пишет "нужную" функцию! Представьте к примеру, что условия задачи изменились, и нужно подсчитать сумму цифр числа? Что тогда? Будете писать очередную "нужную" функцию? А если требуется подсчитать число четных цифр в числе? Опять будете писать "Нужную" функцию?! В моем же случае ничего писать не надо! Все уже написано! Вы можете применить любой алгоритм, который работает со входными итераторами, используя один раз написанный итератор! Повторяю: один раз написанный итератор!Его возможно просто впечатляют! Вы - тот программист, который вместо того, чтобы, допустим, лжин раз написать реверсивный итератор, постоянно пишет новую функцию для решения задачи, которая делается за минуту с помощью реверсивных итераторв! 0