Не проходит 1 тест на информатиксе(неправильный ответ). Последовательность из 0 и 1

Рейтинг: -2Ответов: 3Опубликовано: 16.02.2023

https://informatics.msk.ru/mod/statements/view.php?id=44136&chapterid=207#1 Вот задача И он проходит все, кроме последнего Подскажите, пожалуйста, что не так...

#include <iostream>
#include <vector>
using namespace std;
uint64_t f(int n) {

    static vector <uint64_t> vec = { 0, 2, 3 };
    if (vec.size() > n) { return vec[n]; }
    else {

        uint64_t val_1 = f(n - 1);
        uint64_t val_2 = f(n - 2);
        vec.push_back(val_1 + val_2);
        return (val_1 + val_2);


    }

}




int main()
{
   
    int n = 0;
    cin >> n;
    cout << f(n);

    return 0;
}
c# комбинаторика арифметика длинная-арифметика
Источник: Stack Overflow на русском

Ответы

▲ 3

Написать простенькую длинную арифметику. Вам же кроме сложения реально ничего не нужно!

#include <iostream>
#include <iomanip>

using namespace std;

unsigned long long m = 1000000000000000000ull;

class bilong
{
    unsigned long long h, l;
public:
    bilong(unsigned long long v, unsigned long long V = 0):h(V),l(v){}
    bilong operator+(const bilong& v)
    {
        unsigned long long L = l + v.l;
        unsigned long long H = h + v.h + L/m;
        L %= m;
        return bilong(L,H);
    }
    friend ostream& operator <<(ostream&os, const bilong& b);
};

ostream& operator <<(ostream&os, const bilong& b)
{
    if (b.h)
    {
        os << b.h << setw(18) << setfill('0') << b.l;
    }
    else
        os << b.l;
    return os;
}


bilong f(int n)
{
    if (n == 1) return 2;
    if (n == 2) return 3;
    bilong a = 2, b = 3, c = 0;
    for(int i = 0; i < n-2; ++i)
    {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}


int main(int argc, char * argv[])
{
    int n;
    cin >> n;
    cout << f(n);
}
▲ 0

Ответом будет N+1-ое число фибоначи
При N=100 оно будет больше, чем 2^64 и не влезет в uint64_t

▲ 0

Сложение столбиком не забыли? Не самая эффективная реализация, но для этой задачи сойдет. Числа представлены как строки, add складывает их столбиком:

#include <iostream>
#include <string>

int digit(const std::string &s, size_t i) {
    return (i < s.size()) ? s[s.size() - i - 1] - '0' : 0;
}

std::string add(const std::string &a, const std::string &b) {
    std::string c;
    int carry = 0;
    for (size_t i = 0; carry != 0 || i < a.size() || i < b.size(); ++i) {
        const int s = carry + digit(a, i) + digit(b, i);
        carry = s / 10;
        c.insert(0, 1, static_cast<char>('0' + s % 10));
    }
    return c;
}

std::string f(int n) {
    std::string a = "1";
    std::string b = "1";
    for (int i = 0; i < n; ++i) {
        std::string c = add(a, b);
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n;
    std::cin >> n;
    std::cout << f(n) << '\n';
}

$ g++ -std=c++17 -pedantic -Wall -Wextra -Werror -Wwrite-strings -Wconversion bit_seqs.cpp 

$ echo 100 | ./a.out 
927372692193078999176

Или так:

#include <iostream>

int main() {
    const int N = 21;
    int buffer1[N] = {1, 0};
    int buffer2[N] = {1, 0};
    int n;
    std::cin >> n;
    int *a = buffer1;
    int *b = buffer2;
    for (int i = 0; i < n; ++i) {
        int carry = 0;
        for (int j = 0; j < N; ++j) {
            const int s = carry + a[j] + b[j];
            a[j] = s % 10;
            carry = s / 10;
        }
        int *t = a;
        a = b;
        b = t;
    }
    bool print = false;
    for (int j = N - 1; j >= 0; --j) {
        print = print || b[j] != 0;
        if (print) {
            std::cout << b[j];
        }
    }
    std::cout << '\n';
}

P.S. Кешировать в векторе все значения функции для этой задачи излишне. Двух старших значений достаточно чтобы вычислить следующее.

P.P.S. Настаиваю что f(0) = 1. Не ноль как у вас.

P.P.P.S Упражнение: почему "не самая эффективная реализация"?