Как я могу выяснить, сколько символов в числе? - PullRequest
Новая
       18

Как я могу выяснить, сколько символов в числе?

0 голосов
/ 11 сентября 2018

Таким образом, длина:

int test1 = 1 имеет длину 1 символ

int test2 = 37 имеет длину 2 символа

int test3 = 82342 составляет 5 символов.

Я могу найти длину символов этих int, используя:

int character_len = floor(log10(abs(whatever_vairable_here))) + 1;

Я хочу сосчитать int i = 1; вплоть до n, но в примере кода я просто использовал 20).Есть ли способ узнать общее количество символов, которые я буду использовать, не используя первый цикл while для определения размера, который я должен использовать для malloc.Я пытаюсь выяснить, сколько места мне нужно malloc 

int total_characters_needed = 0;
int i = 1;
while (i <= 20) {
    total_characters_needed += floor(log10(abs(i))) + 1;`
    i++;
}

char *my_numbers_as_a_string = malloc(sizeof(char) * total_characters_needed);

i = 1;
while (i <= 20) {
    sprintf(my_numbers_as_a_string, "%d", i);
    i++;
}

printf("%s\n", my_numbers_as_a_string);
// Should print out:
// 1234567891011121314151617181920
//
// If the above is unread-able its basically
// 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Ответы [ 4 ]

0 голосов
/ 11 сентября 2018

Просто выведите число в строку, а затем посчитайте длину строки? Или это слишком просто? 

int numdigits(int n)
{
    char buf[64];
    return(sprintf(buf,"%d",n));
}
0 голосов
/ 11 сентября 2018

Это больше вопрос головоломки. Вы хотите сохранить последовательность чисел от 1 до некоторого числа x в строке, поэтому вам нужно общее количество всех символов. Например, пусть x = 77867. Таким образом, х - это 5-значное число. Это можно выяснить с помощью цикла, заданного user10334659 .

Первое, на что нужно обратить внимание, это то, что цифры от 1 до 4 цифр в основном заполнены и не зависят от значения x . Таким образом, мы можем сначала вычислить количество символов для этих чисел.

  1. 1-9: однозначные цифры. #numbers = 9. => символы = 9 х 1
  2. 10-99: 2 симв. #numbers = 90. => символов = 90 x 2
  3. 100-999: 3 симв. # цифры = 900. => символы = 900 x 3
  4. 1000-9999: 4 симв. # цифры = 9000. => символов = 9000 x 4

Таким образом, общее количество символов для всех чисел от 1 до максимального y -значное число равно:

9 ( 10^0 x 1 + 10^1 x 2 + ... + 10^(y-1) x y )

Теперь нам просто нужно подсчитать общее число от 10^(y) до x (которое представляет собой (y + 1) -значное число). Для нашего случая 10000 - 77867: #numbers = 67688 => символов = 67688x5.

Сложность времени

Пусть максимальное число будет n. Тогда y + 1 можно рассчитать за O (log (n)) времени. Поиск символов от 1 до y -значного числа также занимает O (log (n)) времени. Наконец, число символов от 10 ^ y до n было найдено за O (1) раз.

Таким образом, этот алгоритм может найти общее количество символов в O (log (n)) времени, в отличие от наивного O (n) временного цикла.

0 голосов
/ 11 сентября 2018

Следующий код вычисляет общее количество цифр в десятичных числах для всех целых чисел от 1 до n: 

int Digits = 0;
int LeadingZeros = 0;
for (int t = n; 0 < t; t /= 10)
{
    ++Digits;
    LeadingZeros = 10*LeadingZeros + 1;
}

int TotalDigits = Digits * (n+1) - LeadingZeros;

Причина: цикл вычисляет количество цифр в n, помещая это число в Digits. Если бы мы записали все целые числа от 0 до n в виде десятичных чисел с Digits цифрами (с использованием начальных нулей, таких как «003»), то было бы использовано Digits * (n+1) цифр. Из этого мы хотим вычесть количество ведущих нулей. (Для нуля мы хотим вычесть все его нули, чтобы он не оказывал никакого влияния на наш счет.)

Для n от 1 до 9 вычитается только один «0», а для 0. Для n от 10 до 99 мы хотим вычесть 9 ведущих нулей из «01» в « 09 », а также два нуля в« 00 ». Таким образом, от 10 до 99 мы вычитаем тот же один ведущий ноль, что и для n в 1 к 9, но также и еще десять ведущих нулей. Аналогично, для n от 100 до 999 мы вычитаем эти ведущие нули плюс еще 100 - еще один для каждого числа от 0 до 99. В конечном счете, число LeadingZeros - это число 111 ... 111 с тем же количеством цифр, что и n. Мы видим, что цикл вычисляет это в LeadingZeros, поэтому общее количество используемых цифр равно Digits * (n+1) - LeadingZeros.

При подготовке буфера для этих цифр, должен быть добавлен еще один символ для завершающего нуля. Кроме того, sprintf(my_numbers_as_a_string, "%d", i); запишет новый номер в начало my_numbers_as_a_string. Для объединения новых номеров необходимо предусмотреть возможность записи до конца предыдущих номеров.

0 голосов
/ 11 сентября 2018

Чтобы подсчитать количество записанных цифр, если вы записываете числа от 1 до n, используйте что-то вроде 

unsigned long digits(unsigned long n) 
{ 
    unsigned long total = 0;  
    for (unsigned long i = 1; i <= n; i *= 10){
        total += (1 + n - i); 
    }
    return total;  
}

Например, n, будучи 11, производит 1234567891011, чтоимеет 13 цифр.

Алгоритм имеет недостаток в том, что он может зацикливаться на достаточно большом n, а обрезание зависит от диапазона unsigned long на вашей платформе.Ограничение n не более ULONG_MAX / 10 - 1 будет достаточным.

...