0

вписываем целое k, должно вывести k цифр(именно цифр) из последовательности 8^n. При n = 11, тоесть k > 56 программа выводит в конце -2147483647, можно ли исправить?

#include <stdio.h>
#include <iostream>
#include <conio.h>

int Count_Pos(unsigned long int number) {  // цикл для выяснения кол-ва цифр в числе
    int p = 1;
    while ((number / (int)pow(10, p)) > 0) {
        p++;
    }
    return p;
}

void func(int k) {
    int s = 0;
    int r;
    unsigned long int q;
    int C;
    for (int i = 0; s < k; i++) {
        q = (int)pow(8, i); //вычисление степеней циклом
        C = Count_Pos(q); //информация о том какое количество цифр в числе
        s = s + C; //общее количество цифр на текущий момент
        if (s > k) { //если кол-во цифр в моменте оказалось больше вводимого в main
            r = s - k; //находим разницу между кол-вом цифр в моменте и вводимого в main
            q = q / (int)pow(10, r); //убираем ненужные цифры с конца
        }
        printf("%lu", q);
    }
}

void main() {
    setlocale(LC_ALL, "RU");
    int k;
    printf("Введите k:");
    scanf_s("%d", &k);
    if (k == 1) {
        printf("1");
    }
    else if (k <= 0) {
        printf("невозможно");
    }
    else {
        func(k);
    }
}
8
  • 2
    можно оттянуть конец, если использовать 64-разрядные числа long long, ну а далее уже длинная арифметика
    – MBo
    Commented 21 окт. 2022 в 13:30
  • формат будет %ld? Commented 21 окт. 2022 в 13:46
  • Насколько я помню, есть зависимость от компилятора и платформы %lld и %I64d
    – MBo
    Commented 21 окт. 2022 в 13:55
  • похоже работает, большое спасибо Commented 21 окт. 2022 в 14:04
  • ОК, тогда оформлю ответом
    – MBo
    Commented 21 окт. 2022 в 14:11

3 ответа 3

3

Диапазон можно увеличить до 8^21, используя 64-разрядные числа long long или unsigned long long

При выводе спецификатор формата %lld или %I64d (u для unsigned)

Если нужен диапазон ещё больше, тогда потребуется библиотека длинной арифметики, например, GMP

3
  • Нет, длинная арифметика не понадобится. :) Commented 21 окт. 2022 в 15:00
  • @StanislavVolodarskiy Ну ведь всё равно понадобилась, хотя и маленькая специализированная ;)
    – MBo
    Commented 21 окт. 2022 в 15:05
  • Школьное умножение на восемь называть длинной арифметикой? Много чести. Commented 21 окт. 2022 в 15:07
3

Развлечёмся - решим задачу без динамической памяти, массивов, циклов и прочих глупостей. И без длинной арифметики. Число представлено в виде односвязного списка десятичных цифр на стеке. Для вычисления и хранения чисел используется рекурсивная функция print_powers. mul_by умножает число на заданный множитель. print печатает цифры и возвращает сколько ещё осталось напечатать:

#include <stdio.h>

typedef struct digit_t digit_t;
struct digit_t {
    unsigned digit;
    digit_t *next;
};

unsigned print(unsigned k, digit_t *n) {
    if (k == 0 || n == NULL) {
        return k;
    }
    putc('0' + n->digit, stdout);
    return print(k - 1, n->next);
}

unsigned mul_by(unsigned factor, digit_t *n) {
    if (n == NULL) {
        return 0;
    }
    const unsigned head = factor * n->digit + mul_by(factor, n->next);
    n->digit = head % 10;
    return head / 10;
}

void print_powers(unsigned b, unsigned k, unsigned carry, digit_t *n) {
    if (carry > 0) {
        digit_t head = {carry % 10, n};
        print_powers(b, k, carry / 10, &head);
        return;
    }
    k = print(k, n);
    if (k > 0) {
        const unsigned carry = mul_by(b, n);
        print_powers(b, k, carry, n);
    }
}

int main() {
    unsigned b, k;
    if (scanf("%u%u", &b, &k) != 2) {
        return 1;
    }
    print_powers(b, k, 1, NULL);
    puts("");
}
$ gcc -std=c11 -pedantic -Wall -Wextra -Werror digits.c 

$ echo 8 60 | ./a.out
186451240963276826214420971521677721613421772810737418248589

$ echo 8 1000000 | ./a.out 
18645124096327682621...44523567526909810144

$ echo 11 30 | ./a.out
111121133114641161051177156119

В этом примере можно разглядеть биномиальные коэффициенты:

$ echo 1010 70 | ./a.out
1101010201001030301000104060401000010510100501000001061520150601000000
0

Для решения данной конкретной задачи очень легко реализовать упрощённую арифметику "больших десятичных чисел" самостоятельно. Ведь по сути всё, что нам нужно из этой арифметики, это только одна операция - умножение большого числа на цифру (которая в нашем случае равна 8).

Так что всё предельно просто: наше большое число - это массив цифр (однобайтового типа char для их хранения вполне достаточно), а так же минимальный набор функций для работы с этим числом: установка в 1, умножение на цифру, вывод в консоль.

#include <stdio.h>
#include <locale.h>

#define MAX_DIGITS 1024     //максимальное число цифр в числе


/*
 * Структура, реализующая "большое десятичное число"
 * По-хорошему, её удобно реализовать в виде класса, но у нас "Си", по-этому по старинке...
 */

typedef struct tagBIG_DECIMAL
{
    int numDigits;
    char digits[MAX_DIGITS];
} BIG_DECIMAL;


/*
 * Следующий код - "методы" структуры BIG_DECIMAL, в стиле старого "Си"...
 */


//Устанавливает число в 1
void BIG_DECIMAL__SetOne(BIG_DECIMAL* pBigDecimal)
{
    pBigDecimal->numDigits = 1;
    pBigDecimal->digits[0] = 1;
}


//Умножает число на цифру
bool BIG_DECIMAL__MulDigit(BIG_DECIMAL* pBigDecimal, char digit)
{
    if ((digit>1) && (digit<10))
    {
        char carry = 0;

        for (int i=0; i< pBigDecimal->numDigits; ++i)
        {
            char newDigit = pBigDecimal->digits[i] * digit + carry;

            if (newDigit < 10)
            {
                carry = 0;
                pBigDecimal->digits[i] = newDigit;
                continue;
            }

            carry = newDigit/10;
            pBigDecimal->digits[i] = newDigit%10;
        }

        if (carry)
        {
            if (pBigDecimal->numDigits == MAX_DIGITS) return false; //переполнение
            pBigDecimal->digits[pBigDecimal->numDigits++] = carry;
        }

        return true;
    }

    if (digit==1) return true;

    if (digit==0)
    {
        pBigDecimal->numDigits = 1;
        pBigDecimal->digits[0] = 0;
        return true;
    }

    //если цифра задана некорректно, просто игнорируем её
    return false;
}


//Выводит число в консоль
void BIG_DECIMAL__print(BIG_DECIMAL* pBigDecimal, int digCount)
{
    char szChars[MAX_DIGITS+1];

    if (digCount <= 0) return;

    digCount = pBigDecimal->numDigits - digCount;
    if (digCount < 0) digCount = 0;

    int idx = 0;
    for (int i=pBigDecimal->numDigits-1; i>=digCount; --i)
        szChars[idx++] = pBigDecimal->digits[i] | 0x30;

    szChars[idx] = '\0';
    printf(szChars);
}


/*
 * Наша цель
 */

void func(int k)
{
    BIG_DECIMAL bigNum;

    BIG_DECIMAL__SetOne(&bigNum);

    while (true)
    {
        int cnt = bigNum.numDigits;
        k-= cnt;
        if (k < 0) cnt+= k;
        BIG_DECIMAL__print(&bigNum, cnt);
        if (k<=0) break; 
        if (!BIG_DECIMAL__MulDigit(&bigNum, 8))
        {
            printf("... (overflow)");
            break;
        }
    }

    printf("\n");
}


int main()
{
    int k;

    setlocale(LC_ALL, "Russian");

    printf("Введите k: ");
    scanf("%d", &k);

    if (k>0)
    {
        func(k);
        return 0;
    }

    printf("невозможно\n");

    return 0;
}

Пример выполнения:

Введите k: 1000
1864512409632768262144209715216777216134217728107374182485899345926871947673654975581388843980465111043518437208883228147497671065622517998136852481801439850948198414411518807585587211529215046068469769223372036854775808737869762948382064645902958103587056517124722366482869645213696377789318629571617095683022314549036572936765442417851639229258349412352193428131138340667952988161547425049106725343623905281237940039285380274899124224990352031428304219919299379279228162514264337593543950336633825300114114700748351602688507060240091291760598681282150440564819207303340847894502572032324518553658426726783156020576256259614842926741381426524816461004820769187434139310514121985316880384166153499473114484112975882535043072132922799578491587290380706028034457610633823966279326983230456482242756608850705917302346158658436518579420528646805647338418769269267492148635364229125444517870735015415413993718908291383296435561429658801233233119497512663310663683484491437270409865864955980101306485309442

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.