Я написал, как знал. Но препод говорит, чтобы я оптимизировал всё это, чтобы сложность программы была sqrt(N), я весь интернет перерыл, но решения не нашёл. Я только на первом курсе, поэтому, пожалуйста, не надо писать функции и операторы, которые слишком крутые для первака. ВВОД : N,ВЫВОД : кол-во пар.
....
int n;
cin >> n;
int k = 0;
int x,y;
int t = pow(n, 0.5);
for (x= 0; x <=t; x++) {
for (y = 0; y <=t; y++) {
if (x * x + y * y < n) {
k += 1;
}
}
}
cout << k;
return 0;
Другие языки программирования и технологии
C++.Обычная задача : найти кол-во пар (x,y) , удовлетворяющих условию X^2+Y^2<N. Помогите оптимизировать.
Это что - шутка такая? Переменную х больше, чем √N раз изменять не придётся - это верно! А переменная у изменяться будет в ещё бóлее узких пределах - от 0 до ~√(N-x²). Но изменяться переменные должны обе, а не лишь одна из них, и в ~√N операций тут никак не уложиться! Тогда причём здесь √N как оценка сложности алгоритма (программа - это тоже алгоритм!). Тут же надо, как я понял, не оценку сделать количества пар, а вычислить их точное (или какое там ещё?) количество! Попробуем так:
#include "iostream"
using namespace std; int main()
{ unsigned long long k=0,n,x,y; for(;;) { cout << "n = ?\b"; cin >> n; for (x=0; x*x < n; x++) for (y=0; y*y < n-x*x; y++) k++; cout << k <<'\n'; } }
При N=1000000000 пар получается 785429715. Можно сыграть на симметрии: (х, у) и (у, х) - пары обе допустимые, если допустима лишь одна из них. Можно, наверно, как-нибудь соптимизировать операции внутри условий цикла. Но всё равно сложность алгоритма для больших N будет где-то 0,78543•N или в два раза меньше, но точно никак ни √N! А вот оценка сверху (то есть приближённое количество пар!) эта очень точная, но для неё вообще одна единственная операция нужна!
P.S. Да, а числа х и у то хоть неотрицательные как у меня? Может быть они целые или натуральные? Даже спрашивать боюсь - а вдруг они вещественные? В задании об этом нет почему-то ни слова, ни полслова!..
#include "iostream"
using namespace std; int main()
{ unsigned long long k=0,n,x,y; for(;;) { cout << "n = ?\b"; cin >> n; for (x=0; x*x < n; x++) for (y=0; y*y < n-x*x; y++) k++; cout << k <<'\n'; } }
При N=1000000000 пар получается 785429715. Можно сыграть на симметрии: (х, у) и (у, х) - пары обе допустимые, если допустима лишь одна из них. Можно, наверно, как-нибудь соптимизировать операции внутри условий цикла. Но всё равно сложность алгоритма для больших N будет где-то 0,78543•N или в два раза меньше, но точно никак ни √N! А вот оценка сверху (то есть приближённое количество пар!) эта очень точная, но для неё вообще одна единственная операция нужна!
P.S. Да, а числа х и у то хоть неотрицательные как у меня? Может быть они целые или натуральные? Даже спрашивать боюсь - а вдруг они вещественные? В задании об этом нет почему-то ни слова, ни полслова!..
Программа у тебя творит что угодно, но только не то, что надо.
Нo это больше из области математики вопрос, а не программирования. Следи за руками:
Очевидно, что количество каждого из натуральных чисел х и у, которые бы удовлетворяли этому условию, будет не больше, чем a=floor(sqrt(n))-1
Таким образом, нам нужно узнать количество комбинаций:
а и 1
(а-1) и 1, 2
(а-2) и 1, 2, 3
...
1 и 2, 3 ...а
Всего 2+3+...+а-1 комбинаций.
Применив формулу суммы арифметической прогрессии ты с легкостью получишь тут линейный алгоритм, не то что от корня.
Дерзай.
Нo это больше из области математики вопрос, а не программирования. Следи за руками:
Очевидно, что количество каждого из натуральных чисел х и у, которые бы удовлетворяли этому условию, будет не больше, чем a=floor(sqrt(n))-1
Таким образом, нам нужно узнать количество комбинаций:
а и 1
(а-1) и 1, 2
(а-2) и 1, 2, 3
...
1 и 2, 3 ...а
Всего 2+3+...+а-1 комбинаций.
Применив формулу суммы арифметической прогрессии ты с легкостью получишь тут линейный алгоритм, не то что от корня.
Дерзай.
Мартин Борман
Да, всё, в принципе, правильно, хороший подход: нужно просто посчитать сумму S{x=0;floor(√n)}[1+floor(√(n-x²)]. Всего 1+floor(√n) слагаемых, но операций-то сколько нужно на вычисление каждого слагаемого? Тут -да! получается сложность ~√N операций, но каких? И хотя взятие корня - сравнительно простая операция, так опять таки разрядная сетка представления чисел в компьютере ограничена и в принципе компьютер при вычислении корня √ с точностью float может скакнуть куда-нибудь не туда - весь этот процесс надо будет тщательно и скрупулёзно контролировать!
Но если как следует наладить надёжность вычислений, то, похоже, тут как раз получается алгоритм сложности ~√N !..
Но если как следует наладить надёжность вычислений, то, похоже, тут как раз получается алгоритм сложности ~√N !..
Похожие вопросы
- Найти трехзначные числа a, b, c, все цифры которых различны и удовлетворяют уравнению a^2 – b^2 – c^2 = a – b – c.
- Excel 2007 x^3+1,41*x^2-5,4724*x-7,380384=0 как решить это уравнение ???=(
- Уравнение a*x+b*y=c
- Паскаль!!)) входной файл содержит два числа x и y. Выходной последнюю цифру числа x в y степени! помогите пожалуйста!
- Вычислить произведение n>=2 (n четное) сомножителей y=(2/1)*(2/3)*(4/3)*(4/5)*(6/5)*(6/7)*..
- объясните как именно работает цикл (int i = 0; i < N; i++) в этом коде, почему нельзя написать i+1, вместо i++
- Помогите написать на ассемблере програму для вычисления виражения y=(c-(d/2)+33 )/(2*a*a-1). c=5,d=6,a=3.
- Определите значение переменных x и y после выполнения фрагмента алгоритма.
- s=loga(x+2)+sqrt(abs(logb(y+2))/(logc(z+2))) в pascal помогите написать процедуру
- Дано функцию f(x,y). Вивести на екран функцію g(x)=∫_a^b▒〖f(x,y)〗 dy. С++
#include "iostream"
#include "cmath"
int main()
{ unsigned long long int k,N,x,y; for(;;) { cout << "N = ?\b"; cin >> N; k=0; for (x=0; x <= floor(sqrt(N)); x++) k+=ceil(sqrt(N-x*x)); cout << k << '\n'; } }
При N=1000000000 количество пар получается 785429715, как и в той программе, так что, вроде, всё правильно. Только та программа при N, равном, например, триллиону и больше, сразу виснет, а эта довольно быстро выдаёт результат, то есть алгоритм точно быстрый!
(А о Юриусе с его галиматьёй даже и говорить не хочу! Где и какую арифметическую прогрессию он тут увидел и почему не понял для чего нужны слагаемые - я не знаю, да, честно говоря, и знать не хочу!)