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

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

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

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

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

@diagon · 06.08.2011, 21:51

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

Глупость! Это как раз подход тех, кого нельзя считать программистами. Программирование - это построение абстракций.

Еще вчера вы были категорически против абстракции =)

А зачем тогда, позвольте вас спросить, разработчики С++ старались и писали стандартные алгоритмы?!

В STL включены только действительно универсальные алгоритмы, поиск максимальной цифры в n-ой системе счисления таким алгоритмом назвать нельзя. И есть разница - разработчики с++ и некий персонаж-с-горы. Если первым вполне можно доверять, то реализацию второго не помешало бы проверить. Вот только быстрее и надежнее свою функцию написать =)

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

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

Еще вчера вы были категорически против абстракции =)

В STL включены только действительно универсальные алгоритмы, поиск максимальной цифры в n-ой системе счисления таким алгоритмом назвать нельзя. И есть разница - разработчики с++ и некий персонаж-с-горы. Если первым вполне можно доверять, то реализацию второго не помешало бы проверить. Вот только быстрее и надежнее свою функцию написать =)

Во-первых, я не знаю, где я был пролтив абстракций. Это скорей всего вы просто путатет божий дар с яичницей! Я был не против абстракций, а говорил про особенности языка С++. А это не одно и тоже. Так что не передергивайте.

Что касается адгоритмов, то о том и идет речь, что они уже написаны! Поэтому почему бы ими не воспользоваться?! Почему вы вмес то стандартных алгоритмов пытаетесь написать собственную функцию поиска максимального элемента? Почему вы вместо стандартного алгоритма будете писать собственную функцию минимального элемента? Почему вы вместо стандартного алгоритма подсчета элементов, удовлетворяющих заданному условию, бцдете писать собственную функцию?! Не проще ли один раз написать итератор, который просто элементарный?! И тогда вы сможете использовать, практически, любой алгоритм С++?

Ваша проблема в том, что вы совершенно не понимаете С++ и мыслите в процедурном стиле! То есть С++ совершенно вас не научил мыслить объектно-ориентированно!

@diagon · 06.08.2011, 22:09

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

Это скорей всего вы просто путатет божий дар с яичницей!

Вот это самооценка

Уважаю!

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

Почему вы вмес то стандартных алгоритмов пытаетесь написать собственную функцию поиска максимального элемента?

Во-первых, не пытаюсь - написал.
Во-вторых, приведите мне код, который делает то же самое.
Я крайне сомневаюсь, что он получится в одну строку.
Вопрос - зачем так извращаться, если мне нужна одна элементарная функция, которая по сложности приблизительно равна а + б?

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

вы совершенно не понимаете С++

Где-то я это уже слышал... Но аргументов так и не дождался.

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

мыслите в процедурном стиле!

Возможно, потому, что задача в процедурном стиле?
Заметьте, в формулировке фигурировало слово "функция".

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

То есть С++ совершенно вас не научил мыслить объектно-ориентированно!

Да, вы правы. Я думаю, все оттого, что с++ неодушевлен. Я пытался его разговорить, но это действительно так.

silent_1991 · 06.08.2011, 22:25

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

@IIIa66uMEM6eP · 07.08.2011, 00:53 **[ТС]**

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

Я вам подсказал очень оригинальную идею, которая никому в голову даже не пришла!

это к той самой теме, где 50 способов написания "Hello world"

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

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

Вам надо написать входной итератор, который возвращает очередную цифру числа. И для этого входного итератора использовать стандартный алгоритм std::max_element.

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

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

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

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

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

@Paporotnik · 07.08.2011, 01:23

не путайте программирование в институте и в реальной работе. в институте ваша цель не получить результат, а понять принцип по которому он получается, т.е. реализовать еще раз то, что было реализовано до вас 100500 раз. в конце концов курс по программированию называется "Алгоритмические языки" или "Объектно-ориентированное программирование", а не "С++ STL".
а в реальной работе все наоборот - стоит максимально использовать уже созданное до тебя. это экономит время и силы.

@easybudda · 07.08.2011, 05:17

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

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

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

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

это к той самой теме, где 50 способов написания "Hello world"

ну это с любой простенькой задачкой так - сразу конкурс извращений начинается...

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

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <math.h>
 
int maxdigit(unsigned num){
    int pwr = (int)log10((double)num);
    int high = num / (int)pow(10.0, pwr);
    return ( pwr ) ? ( num % 10 < high ) ? maxdigit(num / 10) : maxdigit(num - high * (int)pow(10.0, pwr)) : num;
}
 
int main(void){
    unsigned num;
    
    while ( printf("Number: ") && scanf("%u", &num) == 1 )
        printf("Max digit: %d\n", maxdigit(num));
        
    return 0;
}

Не по теме:

на всякий случай: тщательной проверкой ввода неотрицательного числа, количества доступной оперативной памяти и прав пользователя на запуск приложения сознательно не озадачивался ;)

Комментарий модератора

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

@Сыроежка · 07.08.2011, 19:28

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

Вот это самооценка

Уважаю!

Во-первых, не пытаюсь - написал.
Во-вторых, приведите мне код, который делает то же самое.
Я крайне сомневаюсь, что он получится в одну строку.
Вопрос - зачем так извращаться, если мне нужна одна элементарная функция, которая по сложности приблизительно равна а + б?

Где-то я это уже слышал... Но аргументов так и не дождался.

Возможно, потому, что задача в процедурном стиле?
Заметьте, в формулировке фигурировало слово "функция".

Да, вы правы. Я думаю, все оттого, что с++ неодушевлен. Я пытался его разговорить, но это действительно так.

Ваш подход - это сто раз писать сто различных функций и один раз их использовать. Почему один раз? Да потому что как только изменится условие задачи, вам придется писать сто первую функцию! Фактически, вы поступаете следующим образом. Вы всю стандартную библиотеку С++ выкидываете в мусорное ведро и начинаете для частного случая писать частную функцию, которая совершенно не пригодна для ее обобщения.

Давайте рассмотрим, какие могут возникнуть задачи. Например,
1. Это исходная задача - найти максимальную цифру.
Далее могут возникнуть задачи
2. Найти минимальную цифру
3. Найти сумму цифр числа
4. Найти частичные суммы цифр числа
5. Найти произведение цифр числа
6. Найти частичные произведения цифр числа
7. Подсчитать количество четных цифр в числе
8. Подсчитать количество нечетных цифр в числе
10. Найти в числе заданную цифру
11 записать цифра числа в контейнер
12 Получить все перестановки цифр числа
13. Найти первую цифру в числе, которая входит в заданный набор цифр.
и т.д. и т.д.

Для каждой этой задачи вы пишите свою функцию. Даже написание сотни очень простых функций чревато возникновением ошибок. Но все, что я перечислили и мог бы перечислить, уже сделано! Например, чтобы подсчитать количество четных или нечетных цифр в числе, если бы вы имели итератор, можно сделать с помощью алгоритма std::count. Найти заданную цифру в числе можно с помощью алгоритма std::find или std::find_if. Переписать цифры в контейнер можно с помощью алгоритма std::copy и т.д. То есть если бы вы имешли входной итератор, то перед вами открываются неограниченные возможности.

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

Добавлено через 59 секунд

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

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

Хорошая идея, мне она в голову сразу же не пришла.

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

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

это к той самой теме, где 50 способов написания "Hello world"

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

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

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

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

Вас преподаватели ругают, потому что от вас требуют практических занятий, чтобы вы на простых примерах изучали язык. А не оценили вы мою идею именно потому, что решая эти многочисленные задачи, вы за "тремя деревяьми не видите леса"! То есть вы не в состоянии мыслить абстрактно и не понимаете те возможности, которые предоставляет С++. ВЫ сразу же бросаетесь в "рукопашное программирование". То есть, как я уже сказал, у вас отсутствует объектно-ориентированное мышление. В виду слабой квалификации как программиста, вам даже не приходит в голову мысль, как воспользоваться тем арсеналом С++, который имеется в вашем распоряжении, как сделать так, чтобы извлечь максимальную пользу из кода, сделать его универсальным и наделить его той силой, которой обладает С++.

@diagon · 07.08.2011, 19:29

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

Вы всю стандартную библиотеку С++ выкидываете в мусорное ведро и начинаете для частного случая писать частную функцию, которая совершенно не пригодна для ее обобщения.

C чего вы решили, что я не использую алгоритмы STL? Даже в той однострочной функции используется std::max. Но для данного случая они непригодны(я про случай с восьмеричной системой счисления). С десятичной можно просто загнать число в stringstream, считать оттуда строкой и использовать max_element. Ну или без stringstream'a использовать boost::lexical_cast.
Какие-то итераторы писать здесь - лишнее.
А, блин, это же выше меня написали...

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

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

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

@IIIa66uMEM6eP · 07.08.2011, 19:32 **[ТС]**

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

вы не в состоянии мыслить абстрактно и не понимаете те возможности, которые предоставляет С++. ВЫ сразу же бросаетесь в "рукопашное программирование". То есть, как я уже сказал, у вас отсутствует объектно-ориентированное мышление. В виду слабой квалификации как программиста, вам даже не приходит в голову мысль, как воспользоваться тем арсеналом С++, который имеется в вашем распоряжении, как сделать так, чтобы извлечь максимальную пользу из кода, сделать его универсальным и наделить его той силой, которой обладает С++.

я поражаюсь как вы читаете между строк, не замечая сути.

@Сыроежка · 07.08.2011, 19:42

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

C чего вы решили, что я не использую алгоритмы STL? Даже в той однострочной функции используется std::max. Но для данного случая они непригодны(я про случай с восьмеричной системой счисления). С десятичной можно просто загнать число в stringstream, считать оттуда строкой и использовать max_element. Ну или без stringstream'a использовать boost::lexical_cast.
Какие-то итераторы писать здесь - лишнее.
А, блин, это же выше меня написали...

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

Вы не видите разницы между тем 1) использовать алгоритм STL в частной задаче и 2) решить задачу так, чтобы можно было бы использовать любой алгоритм! Вы разницу между двумя этими утверждениями понимаете? То, что вы в своей задаче используете алгоритм, не делает ваше решение гибким и возможным к применению в других обстоятельствах. ВЫ сразу же начинаете прибегать к другим средствам, как использование stringstream. Это сразу же говорит, что ваше исходное решение неудачное! Как только поставленная задача слегка меняется, вам сразу же приходится свое же решение выбрасывать в мусорное ведро и использовать stringstream. Об этом я и веду речь, и чего вы не в состоянии понять.

На самом деле все, что требуется - это получить поток цифр, из которых состоит число. И с этим потоком цифр можно делать все, что угодно. Как получить поток цифр? Это уже другой вопрос. Я предложил написать входной итератор. Наверное можно использовать и stringstream для этих целей. Но в любом случае эта идея основопологающая и продуктивная в отличии от написания частной функции, которую написали, а затем выбросили в мусорное ведро, так как задача слегка изменилась.

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

Jupiter · 07.08.2011, 20:55

Не по теме:

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

Ну или без stringstream'a использовать boost::lexical_cast.

каг бе boost::lexical_cast испотльзует stringstream внутри:)

@easybudda · 07.08.2011, 22:14

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

чтобы мне тут не говорил модератор

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

Вот для разнообразия со строкой пример...

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
char * max_char(const char * buf, size_t size){
    return ( size < 2 ) ? (char*)buf : ( *buf < *(buf + size - 1) ) ? max_char(buf + 1, size - 1) : max_char(buf, size - 1);
}
 
int max_digit(int num){
    static char buf[32];
    
    sprintf(buf, "%d", abs(num));
    return *max_char(buf, strlen(buf)) - '0';
}
 
int main(void){
    int num;
    
    while ( printf("Number: ") && scanf("%d", &num) == 1 )
        printf("Max digit: %d\n", max_digit(num));
    
    return 0;
}

@diagon · 07.08.2011, 22:32

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

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

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

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

каг бе boost::lexical_cast испотльзует stringstream внутри

Странно как-то. Он же работает в разы быстрее stringstream'a
http://www.boost.org/doc/libs/... erformance

@Olga_ · 08.08.2011, 13:30

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

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

Это слишком просто решается на бумаге. Давайте усложним задачу. Вывести на экран все счастливые билеты по увеличению веса:
000000
001001
010010
100100
011011
101101
110110
002002
и т.д.

либо в лексикографическом порядке:
000000
001001
002002
...
009009
010010
и т.д.

@grizlik78 · 08.08.2011, 13:34

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

010010
100100
002002

Да где ж тут лексикографический порядок? Ну надо же явно уточнить, что ведущие нули отбрасываем.

@Olga_ · 08.08.2011, 13:35

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

Да где ж тут лексикографический порядок? Ну надо же явно уточнить, что ведущие нули отбрасываем.

По увеличению веса

@diagon · 08.08.2011, 13:37

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

Это слишком просто решается на бумаге.

Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.

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

Давайте усложним задачу. Вывести на экран все счастливые билеты в лексикографическом порядке

Хм... А что мешает просто отсортировать массив с результатами?

Ну или более сложный вариант этой задачи - найти общее количество n-значных счастливых билетов(n четное, не больше 100). Можно без длинной арифметики, просто алгоритм =)

@grizlik78 · 08.08.2011, 13:39

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

По увеличению веса

А вес это сумма разрядов?

@Olga_ · 08.08.2011, 13:41

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

А вес это сумма разрядов?

Да, именно так

Добавлено через 47 секунд

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

Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.

А кто говорил о таком глупом переборе

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

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@IIIa66uMEM6eP заставил Бендера 854 / 319 / 17 Регистрация: 05.12.2010 Сообщений: 1,707 Записей в блоге: 6

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

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	06.08.2011, 22:25
	Сыроежка, зачем писать итератор, когда можно воспользоваться строковыми потоками и получить то же самое? 0

@Paporotnik 385 / 229 / 12 Регистрация: 06.07.2011 Сообщений: 512
	07.08.2011, 01:23
	не путайте программирование в институте и в реальной работе. в институте ваша цель не получить результат, а понять принцип по которому он получается, т.е. реализовать еще раз то, что было реализовано до вас 100500 раз. в конце концов курс по программированию называется "Алгоритмические языки" или "Объектно-ориентированное программирование", а не "С++ STL". а в реальной работе все наоборот - стоит максимально использовать уже созданное до тебя. это экономит время и силы. 0

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

Решение