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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.96
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
#1

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

06.08.2011, 01:53. Просмотров 5969. Ответов 79
Метки нет (Все метки)

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

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

Алгоритмы для решения - C++
Через какие алгоритмы можно реализовать эти две задачи.

Написать программу решения системы тригонометрических уравнений (разветвляющиеся алгоритмы) - C++
Здравствуйте уважаемые форумчане, требуется ваша помощь. Я немного затрудняюсь в написании кода разветвляющихся алгоритмов, очень прошу...

Задачи на циклические алгоритмы - C++
Помогите пожалуйста сделать в с++: 1)Написать функцию, которая по целому a вычисляет и возвращает максимальное n, при котором n! ≤ a. ...

не знаю решения задачи в c ++ - C++
п. 5.18 Правил Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. Внизу страницы есть редактор формул ...

Алгоритм решения задачи - C++
Помогите пожалуйста сделать алгоритм по коду, из блоков и стрелочек Вот код: //Библиотека контейнера #include<list> //Библиотека...

Алгоритм решения задачи - C++
Есть вот такая вот задача . На дороге в некоторых местах разбросаны золотые монеты. Для каждой монеты известно ее местоположение, которое...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Paporotnik
383 / 227 / 7
Регистрация: 06.07.2011
Сообщений: 512
07.08.2011, 01:23 #46
не путайте программирование в институте и в реальной работе. в институте ваша цель не получить результат, а понять принцип по которому он получается, т.е. реализовать еще раз то, что было реализовано до вас 100500 раз. в конце концов курс по программированию называется "Алгоритмические языки" или "Объектно-ориентированное программирование", а не "С++ STL".
а в реальной работе все наоборот - стоит максимально использовать уже созданное до тебя. это экономит время и силы.
0
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,707
07.08.2011, 05:17 #47
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от 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;
}

Не по теме:

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



 Комментарий модератора 
Сыроежка, Вас, простите, кто назначил определять знания и умственные способности других форумчан? Перечитайте правила форума, особенно ту часть, где про уважительное отношение...
5
Сыроежка
Заблокирован
07.08.2011, 19:28 #48
Цитата Сообщение от 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 минуты

увы, не оценил, я не счетаю это более рациональным решением данной задачи.. мало книг? Да они мне снятся уже, у меня книжная полка плюсами обставлена, не счетая электронной библиотеки.
Вас преподаватели ругают, потому что от вас требуют практических занятий, чтобы вы на простых примерах изучали язык. А не оценили вы мою идею именно потому, что решая эти многочисленные задачи, вы за "тремя деревяьми не видите леса"! То есть вы не в состоянии мыслить абстрактно и не понимаете те возможности, которые предоставляет С++. ВЫ сразу же бросаетесь в "рукопашное программирование". То есть, как я уже сказал, у вас отсутствует объектно-ориентированное мышление. В виду слабой квалификации как программиста, вам даже не приходит в голову мысль, как воспользоваться тем арсеналом С++, который имеется в вашем распоряжении, как сделать так, чтобы извлечь максимальную пользу из кода, сделать его универсальным и наделить его той силой, которой обладает С++.
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.08.2011, 19:29 #49
Цитата Сообщение от Сыроежка Посмотреть сообщение
Вы всю стандартную библиотеку С++ выкидываете в мусорное ведро и начинаете для частного случая писать частную функцию, которая совершенно не пригодна для ее обобщения.
C чего вы решили, что я не использую алгоритмы STL? Даже в той однострочной функции используется std::max. Но для данного случая они непригодны(я про случай с восьмеричной системой счисления). С десятичной можно просто загнать число в stringstream, считать оттуда строкой и использовать max_element. Ну или без stringstream'a использовать boost::lexical_cast.
Какие-то итераторы писать здесь - лишнее.
А, блин, это же выше меня написали...

Цитата Сообщение от Сыроежка Посмотреть сообщение
В виду слабой квалификации как программиста, вам даже не приходит в голову мысль, как воспользоваться тем арсеналом С++, который имеется в вашем распоряжении, как сделать так, чтобы извлечь максимальную пользу из кода, сделать его универсальным и наделить его той силой, которой обладает С++.
Надо же понимать еще, как они работают.
Перейдете вы на какой-нибудь паскаль и сразу же повеситесь без знания элементарных алгоритмов.
0
IIIa66uMEM6eP
заставил Бендера
436 / 292 / 10
Регистрация: 05.12.2010
Сообщений: 1,645
Записей в блоге: 6
07.08.2011, 19:32  [ТС] #50
Цитата Сообщение от Сыроежка Посмотреть сообщение
вы не в состоянии мыслить абстрактно и не понимаете те возможности, которые предоставляет С++. ВЫ сразу же бросаетесь в "рукопашное программирование". То есть, как я уже сказал, у вас отсутствует объектно-ориентированное мышление. В виду слабой квалификации как программиста, вам даже не приходит в голову мысль, как воспользоваться тем арсеналом С++, который имеется в вашем распоряжении, как сделать так, чтобы извлечь максимальную пользу из кода, сделать его универсальным и наделить его той силой, которой обладает С++.
я поражаюсь как вы читаете между строк, не замечая сути.
0
Сыроежка
Заблокирован
07.08.2011, 19:42 #51
Цитата Сообщение от diagon Посмотреть сообщение
C чего вы решили, что я не использую алгоритмы STL? Даже в той однострочной функции используется std::max. Но для данного случая они непригодны(я про случай с восьмеричной системой счисления). С десятичной можно просто загнать число в stringstream, считать оттуда строкой и использовать max_element. Ну или без stringstream'a использовать boost::lexical_cast.
Какие-то итераторы писать здесь - лишнее.
А, блин, это же выше меня написали...


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

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

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

Не по теме:

Цитата Сообщение от diagon Посмотреть сообщение
Ну или без stringstream'a использовать boost::lexical_cast.
каг бе boost::lexical_cast испотльзует stringstream внутри

0
easybudda
Модератор
Эксперт CЭксперт С++
9625 / 5573 / 947
Регистрация: 25.07.2009
Сообщений: 10,707
07.08.2011, 22:14 #53
Цитата Сообщение от Сыроежка Посмотреть сообщение
чтобы мне тут не говорил модератор
Модератор говорит Вам - не судите, да несудимы будете. Кстати, последнее предупреждение, дальше карточки пойдут. Вы бы вместо того, чтобы рассуждать, кто чего не может, а кто чего не умеет, лучше пример своего чудо-итератора привели - вдруг мы все проникнемся и Вас великим гуру признаем...
Вот для разнообразия со строкой пример...
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;
}
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.08.2011, 22:32 #54
Цитата Сообщение от Сыроежка Посмотреть сообщение
То, что вы в своей задаче используете алгоритм, не делает ваше решение гибким и возможным к применению в других обстоятельствах.
А, я таки-понял ваш подход к решению задач. Вы, видимо, немного заработались.
Понимаете, существуют учебные задачи, которые не имеют реального применения. Их цель - обучить решающего базовым алгоритмам. Если вы напишите класс, разбивающий число на цифры и примените к нему max_element/какой либо другой стандартный алгоритм, то так и не поймете алгоритм разбиения числа на цифры с помощью остатка от деления, к примеру. Вы-то, может, его и знаете, но все с чего-то начинали.

Цитата Сообщение от Maxwe11 Посмотреть сообщение
каг бе boost::lexical_cast испотльзует stringstream внутри
Странно как-то. Он же работает в разы быстрее stringstream'a
http://www.boost.org/doc/libs/1_47_0...tm#performance
1
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 13:30 #55
Цитата Сообщение от diagon Посмотреть сообщение
Могу в свою очередь предложить небольшую задачку: нужно посчитать суммарное количество счастливых билетов с асимптотикой хотя бы O(10^3). Впринципе можно и за O(~140) сделать, но это уже сложнее =)
P.S. счастливый билет - это шестизначное число, сумма левых трех цифр которого равна сумме правых трех цифр.
Это слишком просто решается на бумаге. Давайте усложним задачу. Вывести на экран все счастливые билеты по увеличению веса:
000000
001001
010010
100100
011011
101101
110110
002002
и т.д.

либо в лексикографическом порядке:
000000
001001
002002
...
009009
010010
и т.д.
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
08.08.2011, 13:34 #56
Цитата Сообщение от Olga_ Посмотреть сообщение
010010
100100
002002
Да где ж тут лексикографический порядок? Ну надо же явно уточнить, что ведущие нули отбрасываем.
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 13:35 #57
Цитата Сообщение от grizlik78 Посмотреть сообщение
Да где ж тут лексикографический порядок? Ну надо же явно уточнить, что ведущие нули отбрасываем.
По увеличению веса
0
diagon
Higher
1929 / 1195 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
08.08.2011, 13:37 #58
Цитата Сообщение от Olga_ Посмотреть сообщение
Это слишком просто решается на бумаге.
Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.

Цитата Сообщение от Olga_ Посмотреть сообщение
Давайте усложним задачу. Вывести на экран все счастливые билеты в лексикографическом порядке
Хм... А что мешает просто отсортировать массив с результатами?

Ну или более сложный вариант этой задачи - найти общее количество n-значных счастливых билетов(n четное, не больше 100). Можно без длинной арифметики, просто алгоритм =)
0
grizlik78
Эксперт С++
1911 / 1443 / 112
Регистрация: 29.05.2011
Сообщений: 3,000
08.08.2011, 13:39 #59
Цитата Сообщение от Olga_ Посмотреть сообщение
По увеличению веса
А вес это сумма разрядов?
0
Olga_
841 / 183 / 16
Регистрация: 01.08.2011
Сообщений: 502
08.08.2011, 13:41 #60
Цитата Сообщение от grizlik78 Посмотреть сообщение
А вес это сумма разрядов?
Да, именно так

Добавлено через 47 секунд
Цитата Сообщение от diagon Посмотреть сообщение
Ну как просто... Обычный перебор в 6 циклов имеет асимптотику O(10^6).
O(10^3) - перебор только первых трех чисел.
А кто говорил о таком глупом переборе Просто это комбинаторная задачка, количество легче на бумаге найти, а вот вывести все значения гораздо интереснее в том или ином порядке.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.08.2011, 13:41
Привет! Вот еще темы с ответами:

Нужны задачи для их решения - C++
Здравствуйте. Нужны задачи для закрепления изученного материала. Что интересует(с чем я могу работать(база)): &quot;напечатать&quot;, ...

Написать программу на С/С++ решения задачи: - C++
m=min{aij} 1&lt;=i&lt;=n 1&lt;=j&lt;=n

Не могу понять решения задачи - C++
Звучит она так: Составить программу, которая создаёт файл и записывает в него 5 введеных целых чисел. Надеюсь на помощь (и целое...

Проблемы с алгоритмом решения задачи - C++
Нужно написать алгоритм решения задачи. Т.е. что и как делает прога, желательно построчно, ну или близко к этому. Собственно задача: ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.08.2011, 13:41
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru