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

Упрощение и алгоритм - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.93
dlis
0 / 0 / 0
Регистрация: 21.01.2012
Сообщений: 12
21.01.2012, 17:02     Упрощение и алгоритм #1
Здрасте есть рекурентное выражение не удаётся упростить для нахождения итератора, (ВСЯ ПРОБЛЕМА - ЭТО ДВОЙНОЙ ФАКТОРИАЛ) и может поправите алгоритм
C++
1
2
3
4
5
6
7
8
9
10
11
double a,c,sum;
    sum = a=c=x;
    k=1;
    while (fabs(c)>esp)
    {
        c = ??; 
        a*=-c;
        sum+=a;
        k++;
    }
    return sum;
Миниатюры
Упрощение и алгоритм  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.01.2012, 17:02     Упрощение и алгоритм
Посмотрите здесь:

Упрощение кода C++
Упрощение кода C++
C++ Упрощение кода
C++ Упрощение программы
Упрощение кода программы C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.01.2012, 17:55     Упрощение и алгоритм #2
пишете функция нахождения факториала:
C++
1
2
3
4
5
int Factorial(int n)
{
  // вычисления
  return result;
}
Двойной факториал соответственно берется так:
C++
1
int doubleFactorial = Factorial(Factirial(n)); // == n!!
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
21.01.2012, 18:01     Упрощение и алгоритм #3
Мда, жесть !
Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n.
http://ru.wikipedia.org/wiki/Факториал
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.01.2012, 18:09     Упрощение и алгоритм #4
Спасибо, не знал. ну в таком случае надо написать отдельную ф-ию двойного факториала

C++
1
2
3
4
5
int DoubleFactorial(n)
{
  // вычисления
  return result;
}
dlis
0 / 0 / 0
Регистрация: 21.01.2012
Сообщений: 12
21.01.2012, 18:10  [ТС]     Упрощение и алгоритм #5
Цитата Сообщение от odip Посмотреть сообщение
Мда, жесть !
Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1,n], имеющих ту же чётность что и n.
http://ru.wikipedia.org/wiki/Факториал

(2*k)!! = 2^k * k!

8!! = 2^4 * 4! = 384
3!! - ??
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.01.2012, 18:21     Упрощение и алгоритм #6
ну вот как-то так. Надо будет еще всякие граничные случаи наверно обработать. Так же следить, чтобы результат не вылез за возможности типа лонг. + я не знаю что там при делении должно быть.
но идея должна быть понятна. Далее в своих суммах просто вызываете эти ф-ии.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
long Factorial(long n)
{
  // ...
  return 0;
}
 
long DoubleFactorial(long n)
{
  if (n % 2)
  {
    //(2*n + 1)! / (2*n)!!
    return Factorial(2 * n + 1) / DoubleFactorial(2 * n);
  }
  else
  {
    // 2^n * n!
    return (2 << (n - 1)) * Factorial(n);
  }
}
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.01.2012, 18:22     Упрощение и алгоритм #7
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a_{k+1}}{a_k} = - \frac{(4(k+1) - 5)!!}{(4(k+1))!!} \, \frac{(4 k) !!}{(4 k - 5)!!} \, x = - \frac{(4k - 1)!!}{(4k+4)!!} \, \frac{(4 k) !!}{(4 k - 5)!!} \, x = - \frac{(4k - 1)!!}{(4 k - 5)!!} \, \frac{(4 k) !!}{(4k+4)!!} \, x = <br />
= - \frac{(4k - 5)!! (4k - 3) (4k - 1)}{(4k - 5)!!} \, \frac{(4k)!!}{(4k)!! (4k + 2) (4k + 4)} \, x = - \frac{(4k - 3) (4k -1)}{(4k + 2)(4k + 4)} \, x

если ничего не напутал, то так (скобки в числителе и знаменателе раскроешь сам)
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.01.2012, 18:22     Упрощение и алгоритм #8
DU, ты, очевидно, не понял, в чем состоит проблема ТС
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
21.01.2012, 18:27     Упрощение и алгоритм #9
А я вот не пойду зачем вообще считать
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a_{k+1}}{a_k}
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
21.01.2012, 18:29     Упрощение и алгоритм #10
ну да. похоже на то. упростить я воспринял как разбить на ф-ии, а не делать как обычно делают все вычисления в теле цикла. Математическое упрощение - не совсем по теме C/C++
Но все равно имея на руках ф-ии вычисления факториалов упрощать особо и не надо ничего. И без упрощения посчитается.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
21.01.2012, 18:30     Упрощение и алгоритм #11
Можно на каждом шаге считать (4k-5)!!, (4k)!!, x^k, (-1)^(k-1)
Если при этом использовать значения от предыдущего цикла
то будет достаточно быстро считать

Тогда и преобразования делать не нужно
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
21.01.2012, 18:33     Упрощение и алгоритм #12
имея на руках ф-ии вычисления факториалов упрощать особо и не надо ничего
Можно и так
Но факториал очень быстро растет от n
Для хранения результата очень скоро станет мало long int
13 ! = 6 227 020 800
уже не влазит
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.01.2012, 18:35     Упрощение и алгоритм #13
Цитата Сообщение от odip Посмотреть сообщение
А я вот не пойду зачем вообще считать
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a_{k+1}}{a_k}
чтобы выразить http://www.cyberforum.ru/cgi-bin/latex.cgi?a_{k+1} через http://www.cyberforum.ru/cgi-bin/latex.cgi?a_k
Цитата Сообщение от odip Посмотреть сообщение
Можно на каждом шаге считать (4k-5)!!, (4k)!!, x^k, (-1)^(k-1), (-1)^k
Если при этом использовать значения от предыдущего цикла
то будет достаточно быстро считать
ну да, в принципе, хотя эти вычисления как раз и будут аналогичны вычислению
http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a_{k+1}}{a_k} = - \frac{(4k - 3) (4k -1)}{(4k + 2)(4k + 4)} \, x
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
21.01.2012, 18:46     Упрощение и алгоритм #14
Цитата Сообщение от DU Посмотреть сообщение
Математическое упрощение - не совсем по теме C/C++
Но все равно имея на руках ф-ии вычисления факториалов упрощать особо и не надо ничего. И без упрощения посчитается.
а тебя не смущает, что это неэффективно? И что при таком подходе одни и те же факториалы будут вычисляться несколько раз? Нет, конечно, можно вручную кешировать значения функций, но зачем? Да и про переполнение целого типа тебе уже сказали
dlis
0 / 0 / 0
Регистрация: 21.01.2012
Сообщений: 12
22.01.2012, 14:43  [ТС]     Упрощение и алгоритм #15
Вот условие:

Вывести на экран таблицу значений функции Y(x) и её разложение в ряд S(x) с точностью до E. Вывести число итераций, необходимое для достижения заданной точности. Вычисление S(x) и Y(x) оформить в виде функций.

условие прикреплено (скрин 1): нумерация столбцов:
1 - начало промежутка
2 - конец промежутка
3 - сумма
4 - точность
5 - функция.

Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream.h>
#include <math.h>
#include <iomanip.h>
    
    typedef double (*uf)(double, double, int &);
 
void tabl(double, double, double, double, uf);
double y(double, double, int &);
double s(double, double, int &);
 
 
int main()
{
    cout << setw(8) << "x" << setw(15) << "y(x)" << setw(10) << "k" << endl;
    tabl(-0.8, 0.9, 0.1, 0.0001, y);
    cout << endl;
    cout << setw(8) << "x" << setw(15) << "s(x)" << setw(10) << "k" << endl;
    tabl(-0.8, 0.9, 0.1, 0.0001, s);
    return 0;
}
 
 
void tabl(double a, double b, double h, double esp, uf fun)
{
    int k=0;    
    double sum;
    for (double x=a; x<b+h/2; x+=h)
    {
        sum = fun(x, esp, k);
        cout << setw(8) << x << setw(15) << sum << setw(10) << k << endl;
    }
}
 
double y(double x, double esp, int &k)
{
    return pow(x+1,1/4.) - (4-x) / 4.;
}
 
double s(double x, double esp, int &k)
{
    double a,c,sum;
    sum = a = c =  - (x*x) / 128.; 
    k=3;
    while (fabs(c)>esp)
    {
        c =  (-1.0) * ((4*k-3)*(4*k-1))/((4*k+4)*(4*k+2)) * x;  // pow(x,2) / (2*k*(2*k+1));    
        a*=-c;
        sum+=a;
        k++;
    }
    return sum;
}
получается какая-та фигня (скрин2)
Миниатюры
Упрощение и алгоритм   Упрощение и алгоритм  
dlis
0 / 0 / 0
Регистрация: 21.01.2012
Сообщений: 12
23.01.2012, 15:32  [ТС]     Упрощение и алгоритм #16
Быть может неверно рассчитано первое слагаемое суммы?? Дайте совет!!
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2012, 17:09     Упрощение и алгоритм
Еще ссылки по теме:

Упрощение кода C++
Упрощение дробей C++
Упрощение вложенных циклов C++

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

Или воспользуйтесь поиском по форуму:
Nameless One
Эксперт С++
 Аватар для Nameless One
5755 / 3404 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
23.01.2012, 17:09     Упрощение и алгоритм #17
Немного исправил твою функцию, считающую данное выражение через разложение в ряд:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define FIELD_WIDTH 15
#define SEPARATOR(CNT)              \
    do {                    \
    size_t i, j;                \
    putchar('+');               \
    for(i = 0; i < CNT; ++i, putchar('+'))  \
    for(j = 0; j < FIELD_WIDTH; ++j)        \
    putchar('-');               \
    putchar('\n');              \
    } while(0)
    
typedef double (*func_t)(double, double, size_t*);
 
void tabulate(double min, double max, double step,
          double tol, func_t fun, func_t expansion)
{
    /* display header */
    SEPARATOR(4);
    printf("|%*s |%*s |%*s |%*s |\n", FIELD_WIDTH - 1, "x",
       FIELD_WIDTH - 1, "y(x)", FIELD_WIDTH - 1, "s(x)",
       FIELD_WIDTH - 1, "k");
    SEPARATOR(4);
 
    for(; min <= max; min += step)
    {
    size_t step_counter;
    double fun_value = fun(min, tol, NULL),
        exp_value = expansion(min, tol, &step_counter);
 
    printf("|%-*.1f|%-*.5f|%-*.5f|%-*zu|\n", FIELD_WIDTH, min,
           FIELD_WIDTH, fun_value, FIELD_WIDTH, exp_value,
           FIELD_WIDTH, step_counter);
    SEPARATOR(4);
    }
}
 
double y(double x, double tol, size_t* ptr_cnt)
{
    return pow(x + 1, .25) + (x - 4) / 4.;
}
 
double s(double x, double tol, size_t* ptr_cnt)
{
    double sum, addend;
    
    sum = 0;
    addend = - (x * x) / 128.;
 
    *ptr_cnt = 2;
 
    while(fabs(addend) > tol)
    {
    double k = *ptr_cnt;
    sum += addend;
    addend *= (- x) * ((4 * k - 3) * (4 * k - 1)) / ((4 * k + 2) * (4 * k + 4));
    
    ++(*ptr_cnt);
    }
 
    return sum;
}
 
int main(void)
{
    tabulate(-.8, .9, .1, 1e-4, y, s);
            
    exit(0);
}
Но у меня тоже значения функции и ее разложения не совпадают.
Мне кажется, что у тебя в задании дано неправильное разложение функции в ряд. Об этом можно судить аналитически:
при http://www.cyberforum.ru/cgi-bin/latex.cgi?|x| < 1 ряд будет убывающим по модулю. Первое слагаемое ряда (а оно у тебя посчитано правильно) на несколько порядков меньше (по модулю) значения функции. Т.к. для данных http://www.cyberforum.ru/cgi-bin/latex.cgi?x у тебя каждый последующий член ряда будет еще меньше (по модулю), а ряд — знакочередующийся, то очевидно, что модуль суммы ряда не превысит модуля первого слагаемого (которое много меньше точного значения функции).
Уточни у преподавателя задание. Может действительно разложение неправильное или под двойным факториалом в данном случае подразумевается что-то другое.
PS. То, что выражение http://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{a_{k+1}}{a_k} правильное, можно доказать, а в том, что функция s считает именно заданную сумму, можно убедиться, вручную посчитав несколько первых слагаемых суммы и сравнив их со значениями, которые можно просмотреть в отладчике
Yandex
Объявления
23.01.2012, 17:09     Упрощение и алгоритм
Ответ Создать тему
Опции темы

Текущее время: 14:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru