С++ программирование, цикл

@luiza-05 · Регистрация: 04.04.2011

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

Найти 10 первых натуральных чисел, оканчивающихся на цифру 7, кратных числу 9 и больших 100

@diagon · 01.05.2011, 19:42

C++

#include <iostream>
int main(){
    for (int i = 107, c=0;  c< 10; i+=10) {
        if (i%9==0) {
            std::cout << i << ' ';
            c++;
        }
    }
    return 0;
}

@asics · 01.05.2011, 19:48

C++

#include <iostream>
 
bool is_corr(const int &a){
  return a % 10 == 7 && !(a % 9);
}
 
int main(){
  size_t cnt = 0;
  for(int i = 101; cnt != 10; ++i)
    if(is_corr(i)){
      std::cout << i << ' ';
      ++cnt;
    }
  return 0;
}

@diagon · 01.05.2011, 20:29

Хотя еще быстрее будет так

C++

#include <iostream>
int main(){
    for (short i = 117, c=0;  c< 10; i+=90) {
        std::cout << i << ' ';
        c++;
    }
    return 0;
}

Добавлено через 34 минуты
Есть небольшой вопросик...
Ради интереса я прогнал код от asics и справнил его скорость со своим.
И, собственно, я не недоумении.
Теоретически моя программа должна выигрывать по скорости более чем в 100 раз, но на деле оказалось, что скорость программ практически равна.
Почему?...

@ForEveR · 01.05.2011, 20:33

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

@diagon · 01.05.2011, 20:35

Я поставил условие на первые 100000 чисел.
И у asics цикл проверяет каждое число на кратность девяти и последнюю цифру, у меня же банально увеличивает i на 90 и выводит ее.

@ForEveR · 01.05.2011, 20:38

diagon, Ну и на сколько разница? Чем проверяли? Да и какой смысл зацикливаться на оптимизации, которая в данном случае уж точно никому не нужна?

Знаете закон преждевременной оптимизации? Он звучит просто.

Не делай этого!

@diagon · 01.05.2011, 20:39

Секундумером на наручных часах=) В обоих случаях приблизительно 8 секунд, разницы нету.
Я сейчас динамическое программирование изучаю. Какой от него смысл в таком случае?

@neske · 01.05.2011, 20:46

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

Я сейчас динамическое программирование изучаю. Какой от него смысл в таком случае?

Это отдельный способ решения задач в олимпиадном программировании, причем очень полезный.
Только я не пойму, зачем вы привели это сюда.
Зачем рекурсия ? (подобный вопрос).

@diagon · 01.05.2011, 20:49

Ну смотри, казалось бы, в первое случае одна итерация цикла выполняется меньше времени, во втором больше. В первом случае итераций происходит в 90 раз меньше, чем во втором. И тем не менее, скорость работы программ равна. Зачем нужно оптимизировать программу по времени, если нету эффекта?
Насчет рекурсии интересный вопрос, я могу сказать только, что это красивее, так как по скорости значительно проигрывает линейному перебору.

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

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

Ну это есть не что иное, как динамическое программирование. Зачем выполнять проверку для каждого числа больше ста, если все эти числа-арифметическая последовательность?

@Kastaneda · 01.05.2011, 20:49

diagon, тут еще вот какое дело - не факт, что компилятор скомпилировал код именно в таком виде, как он выглядет в С (компилятор мог оптимизировать код, по своему усмотрению, в т.ч. сделать ф-цию inline). Нужно посмотреть ассемблерный код, что бы понять в чем дело.

@ForEveR · 01.05.2011, 20:51

diagon, Олимпиадные задачи обычно не столь тривиальны и там действительно нужно динамическое программирование или другие пути, но никак не в лоб.

@diagon · 01.05.2011, 20:53

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

diagon, тут еще вот какое дело - не факт, что компилятор скомпилировал код именно в таком виде, как он выглядет в С (компилятор мог оптимизировать код, по своему усмотрению, в т.ч. сделать ф-цию inline). Нужно посмотреть ассемблерный код, что бы понять в чем дело.

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

diagon, Олимпиадные задачи обычно не столь тривиальны и там действительно нужно динамическое программирование или другие пути, но никак не в лоб.

Знаю, бывал на таких=)

@Kastaneda · 01.05.2011, 20:58

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

но в данном случае практически разные алгоритмы.

Ну и что? Тут вообще цикл с заранее известными константами, компилятор мог это все превратить в :

C

printf(...);
printf(...);
printf(...);
printf(...);
//и так 10 раз

@diagon · 01.05.2011, 21:01

Т.е. он самостоятельно нашел последовательность? Забавно...

@Kastaneda · 01.05.2011, 21:04

Не по теме:

Реальный случай: люди проверяли 2 разных компилятора, написали длинный код, с кучей математических вычислений, скомпилировали и в результате, программа скомпилированная на одном из компиляторов работала мнгновенно (чего не могло быть вообще). Когда посмотрели ассемблерный код, выяснялось, что по скольку вычисления были с константами, компилятор из длинного кода сделал одну строку - вывод конечного результата )))

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

Не по теме:

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

Т.е. он самостоятельно нашел последовательность? Забавно...

Это предположение... Я не занимался глубоко подобными вещами.

@diagon · 01.05.2011, 22:02

Специально скачал Devcpp, отключил там всю оптимизацию... Обе проги работают в 2 раза быстрее чем на билдере(о_О), но тоже одинаковое количество времени.

@ForEveR · 01.05.2011, 22:06

diagon, Откровенно говоря компилятор вообще многое может сделать на стадии компиляции. Факториал посчитать к примеру.

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.05.2011, 20:51	12
	diagon, Олимпиадные задачи обычно не столь тривиальны и там действительно нужно динамическое программирование или другие пути, но никак не в лоб. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 20:53	13
	Сообщение от Kastaneda diagon, тут еще вот какое дело - не факт, что компилятор скомпилировал код именно в таком виде, как он выглядет в С (компилятор мог оптимизировать код, по своему усмотрению, в т.ч. сделать ф-цию inline). Нужно посмотреть ассемблерный код, что бы понять в чем дело. Компиляторы, конечно, нынче умные пошли, но в данном случае практически разные алгоритмы. diagon, Олимпиадные задачи обычно не столь тривиальны и там действительно нужно динамическое программирование или другие пути, но никак не в лоб. Знаю, бывал на таких=) 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 21:01	15
	Т.е. он самостоятельно нашел последовательность? Забавно... 0

@Kastaneda 5231 / 3204 / 362 Регистрация: 12.12.2009 Сообщений: 8,113 Записей в блоге: 2
	01.05.2011, 21:04	16
	Не по теме: Реальный случай: люди проверяли 2 разных компилятора, написали длинный код, с кучей математических вычислений, скомпилировали и в результате, программа скомпилированная на одном из компиляторов работала мнгновенно (чего не могло быть вообще). Когда посмотрели ассемблерный код, выяснялось, что по скольку вычисления были с константами, компилятор из длинного кода сделал одну строку - вывод конечного результата ))) Добавлено через 1 минуту Не по теме: Сообщение от diagon Т.е. он самостоятельно нашел последовательность? Забавно... Это предположение... Я не занимался глубоко подобными вещами. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.05.2011, 22:06	18
	diagon, Откровенно говоря компилятор вообще многое может сделать на стадии компиляции. Факториал посчитать к примеру. 1

@luiza-05 1 / 1 / 0 Регистрация: 04.04.2011 Сообщений: 12
		1
	С++ программирование, цикл 01.05.2011, 19:38. Показов 1481. Ответов 17 Метки нет (Все метки) Найти 10 первых натуральных чисел, оканчивающихся на цифру 7, кратных числу 9 и больших 100 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.05.2011, 20:33	5
	diagon, Потому что компы сейчас мощные и выполняют такие операции очень быстро. Откуда ж тут разнице то взяться? Всего-навсего цикл + проверка на совпадение условию.. 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 20:35	6
	Я поставил условие на первые 100000 чисел. И у asics цикл проверяет каждое число на кратность девяти и последнюю цифру, у меня же банально увеличивает i на 90 и выводит ее. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	01.05.2011, 20:38	7
	diagon, Ну и на сколько разница? Чем проверяли? Да и какой смысл зацикливаться на оптимизации, которая в данном случае уж точно никому не нужна? Знаете закон преждевременной оптимизации? Он звучит просто. Не делай этого! 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 20:39	8
	Секундумером на наручных часах=) В обоих случаях приблизительно 8 секунд, разницы нету. Я сейчас динамическое программирование изучаю. Какой от него смысл в таком случае? 0

@neske 1552 / 918 / 193 Регистрация: 26.03.2010 Сообщений: 3,105
	01.05.2011, 20:46	9
	Сообщение от diagon Я сейчас динамическое программирование изучаю. Какой от него смысл в таком случае? Это отдельный способ решения задач в олимпиадном программировании, причем очень полезный. Только я не пойму, зачем вы привели это сюда. Зачем рекурсия ? (подобный вопрос). 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 20:49	10
	Ну смотри, казалось бы, в первое случае одна итерация цикла выполняется меньше времени, во втором больше. В первом случае итераций происходит в 90 раз меньше, чем во втором. И тем не менее, скорость работы программ равна. Зачем нужно оптимизировать программу по времени, если нету эффекта? Насчет рекурсии интересный вопрос, я могу сказать только, что это красивее, так как по скорости значительно проигрывает линейному перебору. Сообщение от neske Только я не пойму, зачем вы привели это сюда. Ну это есть не что иное, как динамическое программирование. Зачем выполнять проверку для каждого числа больше ста, если все эти числа-арифметическая последовательность? 0

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	01.05.2011, 22:02	17
	Специально скачал Devcpp, отключил там всю оптимизацию... Обе проги работают в 2 раза быстрее чем на билдере(о_О), но тоже одинаковое количество времени. 0