Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.73/11: Рейтинг темы: голосов - 11, средняя оценка - 4.73
0 / 0 / 0
Регистрация: 10.08.2018
Сообщений: 1

Длинная арифметика: вывести n чисел Фибоначчи

10.08.2018, 20:19. Показов 2428. Ответов 15
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Вывести в консоль n чисел Фибоначчи без переполнения
C
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
 
int main()
{
    unsigned long long n = 256, i = 0, j = 1;
    while(n > 0)
    {
        printf("%llu %llu ", i, j);
        j += i += j;
        n -= 2;
    }
    return 0;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
10.08.2018, 20:19
Ответы с готовыми решениями:

Длинная арифметика. Вычитание двух положительных чисел
Доброго времени суток! У меня не получается сделать вычитание двух длинных положительных чисел... Пыталась разбираться по чужим кодам -...

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

Длинная арифметика
Необходимо реализовать операции сложения, вычитания и умножения двух чисел a и b. Каждое число содержит не более 10000 десятичных знаков,...

15
Модератор
Эксперт по электронике
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
10.08.2018, 20:45
Цитата Сообщение от MRcoder Посмотреть сообщение
j += i += j;
нет ли здесь UB?
0
698 / 140 / 57
Регистрация: 20.08.2017
Сообщений: 255
10.08.2018, 21:21
ValeryS, нет. Сначала к i компилятор прибавит j, затем уже новое значение i прибавит к j.

C
1
2
3
4
int i = 3;
int j = 1;
    
j += i += j;
Assembler
1
2
3
4
5
6
7
mov DWORD PTR [rbp-4], 3 ; int i = 3;
mov DWORD PTR [rbp-8], 1 ; int j = 1;
 
mov eax, DWORD PTR [rbp-8] ; помещаем в EAX значение переменной j.
add DWORD PTR [rbp-4], eax ; прибавляем к i значение EAX (j).
mov eax, DWORD PTR [rbp-4] ; помещаем значение i в EAX.
add DWORD PTR [rbp-8], eax ; прибавляем к j значение EAX (i).
0
Модератор
Эксперт по электронике
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
10.08.2018, 21:38
Цитата Сообщение от Eanmos Посмотреть сообщение
, нет.
откуда такая уверенность? точка следования одна
вот кусочек из статьи
Стандарт как-то очень нечетко описывает такую ситуацию. Он говорит, что операция должна происходить справа налево, но ничего не говорит дополнительно по поводу того, когда должен быть результат этой операции записан в переменную.
http://alenacpp.blogspot.com/2... oints.html
Цитата Сообщение от Eanmos Посмотреть сообщение
Assembler
ассемблерный листинг ни о чем не говорит, один компилятор поведет себя так, другой по другому, даже один и тот же может повести себя по разному при разных ключах оптимизации
Неопределенное поведение
1
Диванный эксперт
Эксперт С++
 Аватар для Max Dark
2550 / 2064 / 971
Регистрация: 09.10.2013
Сообщений: 4,793
Записей в блоге: 4
10.08.2018, 21:46

Не по теме:

Цитата Сообщение от MRcoder Посмотреть сообщение
j += i += j;
Цитата Сообщение от Eanmos Посмотреть сообщение
нет.
Одну строку в коде пожалели...
Писать код нужно так, чтобы через полгода+ не нужно было задумываться самому над тайным смыслом.


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

Добавлено через 4 минуты
ЗЫ: Числа можно представлять в разных системах исчисления.
Для компьютера удобнее всего СИ кратные двум.
0
698 / 140 / 57
Регистрация: 20.08.2017
Сообщений: 255
10.08.2018, 22:54
ValeryS, выдержка из пункта 6.5.16 3 (C11):

The side effect of updating the stored value of the left operand is sequenced after the value computations of the left and rigths operands. The evaluations of operands are unsequenced.
Т. е. точка следования установится после вычисления значения обоих операндов, а порядок вычисления операндов не определен.

В то же время в статье, которую ты привел, говорится:

Если программа пытается модифицировать одну переменную дважды не пересекая точку следования, то это ведет к undefined behavior.
Но наша программа не пытается модифицировать одну переменную дважды, не пересекая точку следования! У нас изменяются только две разные переменные по одному разу:

C
1
j = j + (i = i + j);
Да и, в данном случае, не важен порядок вычисления в операндов обоих операторах присваивания.

По-моему, так.
0
Диссидент
Эксперт C
 Аватар для Байт
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
10.08.2018, 23:23
Я не очень понимаю смысл стартового поста. Человек просит помощи или хочет похвастаться? На первый вариант не очень похоже. Во втором варианте хотелось бы убедиться, что 2128 > ((sqrt(5) + 1)/2sqtr(5))256. А если это так, то до какого значения n этот код будет работать корректно.
Ну, и какова разрядность long long на используемом компьютере и компиляторе.
А хвастаться конструкцией типа
C
1
j += i += j;
лично я бы не стал. Хотя тут вопрос чисто эстетический.
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
10.08.2018, 23:30
какой нафиг UB? может теперь ещё выражения вида a=b=c запишем в UB и будем избегать?
вот ссылаются люди на статью, но из статьи почему-то делают неверный вывод?
вместо "есть такое UB блаблабла между точками следования, его надо избегать в таких-то и таких-то случаях"
делается вывод "в каких-то там случаях бывает UB - а ну его, от греха подальше, давайте вообще всегда все выражения расписывать гораздо подробнее и проще как для первоклассников, пофиг в каких конкретно!"
0
Супер-модератор
Эксперт функциональных языков программированияЭксперт Python
 Аватар для Catstail
38161 / 21096 / 4306
Регистрация: 12.02.2012
Сообщений: 34,680
Записей в блоге: 14
10.08.2018, 23:58
2128=340282366920938463463374607431768211456
https://www.cyberforum.ru/cgi-bin/latex.cgi?({(1+\sqrt{5})/(2\sqrt{5})})^{256}=1.07814047146536E-36
0
1 / 1 / 1
Регистрация: 11.08.2018
Сообщений: 1
11.08.2018, 03:01
Лучший ответ Сообщение было отмечено Kuzia domovenok как решение

Решение

Я считаю, что вам проще будет сменить язык, например, на python:
Python
1
2
3
4
5
6
def fibonacci(n):
    f = [0, 1]
    for i in range(2, n):
        f.append(f[i - 1] + f[i - 2])
    print(f)
fibonacci(256)
1
Модератор
Эксперт по электронике
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
11.08.2018, 09:00
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
ещё выражения вида a=b=c запишем в UB
а что нет что ли?
выражение типа
C
1
a=b=c;
гарантирует что a и b будут равны с на следующей строчке, то бишь после точки с запятой
но какое из присвоений произойдет раньше?
то ли
C
1
2
a=c;
b=c;
то ли
C
1
2
b=c;
a=c;
Цитата Сообщение от Eanmos Посмотреть сообщение
По-моему, так.
ну и ладно
но я бы таких конструкций избегал "Обжегшийся на молоке дует на воду" пару раз сталкивался когда программа вела себя в релизе не так как в отладчике
0
698 / 140 / 57
Регистрация: 20.08.2017
Сообщений: 255
11.08.2018, 09:48
Цитата Сообщение от ValeryS Посмотреть сообщение
гарантирует что a и b будут равны с на следующей строчке, то бишь после точки с запятой
но какое из присвоений произойдет раньше?
На самом деле, тут тоже все однозначно. Цитата из K&R II:

Следующая строка обнуляет сразу три переменные:

C
1
nl = nw = nc = 0;
Это не какая-нибудь специальная форма присваивания, а прямое следствие того факта, что оператор присваивания является выражением, имеющим значение, и что присваивание выполняется справа налево. Можно было бы записать и так:

C
1
nl = (nw = (nc = 0));
0
Модератор
Эксперт по электронике
8978 / 6744 / 921
Регистрация: 14.02.2011
Сообщений: 23,852
11.08.2018, 09:58
Цитата Сообщение от Eanmos Посмотреть сообщение
Следующая строка обнуляет сразу три переменные:
ключевое слово " сразу",но сразу то ничего не бывает всегда что то за чем то
да в 99.99% это без разницы, и можем считать что обнулились сразу, но есть и 00.01 когда порядок может быть важен
1
698 / 140 / 57
Регистрация: 20.08.2017
Сообщений: 255
11.08.2018, 10:09
Цитата Сообщение от ValeryS Посмотреть сообщение
ключевое слово " сразу",но сразу то ничего не бывает всегда что то за чем то
да в 99.99% это без разницы, и можем считать что обнулились сразу, но есть и 00.01 когда порядок может быть важен
Мне кажется, ты не совсем понял. Смотри:

C
1
nl = nw = nc = 0;
Сначала компилятор присвоит nc 0. Вместо nc = 0 можем смело подставить 0 (в уме), т. к. операторы присваивания являются выражениями. 6.5 Expressions / 6.15.16 Assignment operators (C11):

An assignment expression has the value of the left operand after the assignment, but is not lvalue.
Теперь у нас (опять же, в уме) получается следующая картина (nc уже равно нулю):

C
1
nl = nw = 0;
И здесь по аналогии — сначала компилятор присвоит nw 0. Вместо nw = 0 опять подставляем ноль:

C
1
nl = 0;
Абсолютно валидная конструкция в C и порядок присваиваний тут точно определен стандартом.
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
11.08.2018, 11:37
Цитата Сообщение от ValeryS Посмотреть сообщение
но какое из присвоений произойдет раньше?
то ли
C
1
2
a=c;
b=c;
то ли
C
1
2
b=c;
a=c;
C++
1
2
a=b=c;
operator = ( a, operator =(b,c) );
что тут в принципе неоднозначного? обычные правила приоритета операторов работают. О том я и говорю - не надо любую "некрасивую конструкцию" подозревать в UB просто за то, что оно случается в других похожих конструкциях.
0
192 / 166 / 82
Регистрация: 01.07.2016
Сообщений: 943
13.08.2018, 11:40
Цитата Сообщение от Cookieasy Посмотреть сообщение
Python
1
for i in range(2, n):
Python
1
range(2, n + 1) # [2;n + 1)
Добавлено через 33 минуты
По теме:
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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <locale.h>
 
const int MAX_SIZE = 1000;
const int BASE = 1e9;
 
void print_long(const int *);
void sum_fib(int *, int *, int *);
void eq(int *, const int *);
 
void print_long(const int *a) {
    int i = MAX_SIZE - 1, j;
    while(!a[i] && i) {
        --i;
    }
    printf("%d", a[i--]);
    for(j = i; j > -1; --j) {
        int d = BASE / 10;
        while(d) {
            printf("%d", a[j] / d % 10);
            d /= 10;
        }
    }
    printf("\n");
}
 
void sum_fib(int *f1, int *f2, int *f) {
    int c = 0, i;
    for(i = 0; i < MAX_SIZE; ++i) {
        c = f1[i] + f2[i] + c;
        f[i] = c % BASE;
        c /= BASE;
    }
    eq(f1, f2);
    eq(f2, f);
}
 
void eq(int *a, const int *b) {
    int i;
    for(i = 0; i < MAX_SIZE; ++i) {
        a[i] = b[i];
    }
}
 
int main(void) {
    setlocale(LC_ALL, "rus");
    int n, i;
    scanf("%d", &n);
    int f1[MAX_SIZE], f2[MAX_SIZE], f[MAX_SIZE];
    memset(f1, 0, MAX_SIZE * sizeof(int));
    memset(f2, 0, MAX_SIZE * sizeof(int));
    memset(f, 0, MAX_SIZE * sizeof(int));
    f1[0] = 0;
    f2[0] = 1;
    for(i = 2; i <= n; ++i) {
        sum_fib(f1, f2, f);
    }
    print_long(f);
    return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
13.08.2018, 11:40
Помогаю со студенческими работами здесь

Длинная арифметика на Си
Здравствуйте, форумчане! Хотелось бы мне начать топик, сообщения в котором я планирую пополнять постоянно (по возможности и уровню...

Длинная арифметика
Доброе время суток. Я разбираю длинную арифметику. И есть некоторые вопросы. К примеру возьмем Сложение. int a, b, length, i=0,...

Простая Длинная арифметика
Доброго времени суток! У меня задача. Вводим 3 числа,достаточно больших,чтобы они не помещались в стандартные типы данных. Далее надо...

Умножение (длинная арифметика)
Работа с массивами из десяти элементов в 12-ричной системе, реализация функции умножения Результатом возвращается число, указанное в...

Арифметические действия (длинная арифметика)
Хай програмеры!!!! кто может помогите мне с таким заданием: Написать программу, которая выполняет указанные арифметические действия...


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

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Новые блоги и статьи
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .
Фото: Daniel Greenwood
kumehtar 13.11.2025
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru