Сохранение сгенерированных целых чисел в массив для создания строки

Question

Я видел проблему, когда говорят, что есть строка, состоящая из чисел типа "123456789101112131415 ... k" , где k - ввод от пользователя. k - единственный вход здесь. Строка генерируется на основе ввода. Предположим, я ввожу 11. Строка будет "1234567891011" . Указано сгенерировать k-й элемент строки. Например, для k = 21 выходной сигнал будет 5.

В C ++ я действительно могу создать массив строкового типа и сохранить в нем целые числа из цикла for с помощью функции to_string . Но я на самом деле в растерянности, как это сделать на C. Единственное, что я знаю о сканировании строки в массив, это:

scanf(" %[^\n]", array); 

источник: : https://codeforces.com/problemset/problem/1177/A

Я новичок в C. Любая помощь будет признательна ...

Answer 1

Как я уже упоминал в своем комментарии, это больше вопрос проектирования алгоритма, чем программирования на C или обработки строк.Возможно, самый простой способ приблизиться к этому - представить строку как состоящую из нескольких «блоков» чисел.

• блок 1 состоит из чисел 1 - 9 и начинается со смещения 0
• блок 2 содержит числа 10 - 99 и начинается со смещения 9
• блок 3 содержит числа 100 - 999 и начинается со смещения 189
• и т. д.

Поскольку мыЗная смещение каждого блока, мы можем вычислить смещение в блоке , которому соответствует глобальное смещение k.

Например, если k = 207, мы знаем, что соответствующая цифра должнаначинаются в блоке 3 (диапазон номеров от 100 до 999) и что его смещение в этом блоке равно 207 - 189 = 8.Поскольку каждое число в этом блоке имеет 3 цифры, смещение 8 должно соответствовать третьему числу в блоке - то есть 102.А так как остаток от 8, деленный на 3, равен 2, мы знаем, что ищем третью цифру в этом номере (индексы начинаются с 0).

Картинка поможет объяснить это - но уже поздно, поэтому...

В коде ...

static char find_kth_digit(int k) {
    int offset = 0;        // Global offset
    int block_length = 0;  // Length of current 'block'
    int offset_inner = 0;  // Offset within current block
    // Power to which 10 is currently raised
    int l = 1;
    int start = 1, end = 10;  // start / end of current block
    char digit = '0';         // result

    if (k == 0) { 
        return -1;
    }

    // Our indices start at 0 - while the question demands they begin at 1.
    k--;

    while (l < 5) {  // Only required to go up to k = 10000
        end = start * 10;
        offset_inner = k - offset;
        // How many digits overall in the current block of numbers?
        block_length = l * (end - start);
        // Update global offset
        offset = offset + block_length;
        // Is k within these block?
        if (k < offset) {
            int n = start + offset_inner / l;
            int d = offset_inner % l;
            return kth_digit_from_end_of_n(n, l - d);
        }
        l++;
        start = end;
    }

    if (l == 5) {
        return -1;
    }

    return digit;
}

Помощник для поиска определенной цифры в числе ...

static char kth_digit_from_end_of_n(int n, int k) {
    char c = '0';
    while (k--) {
        c = n % 10;
        n /= 10;
    }
    return c + '0';
}

Обратите внимание, что - внутри -алгоритм использует индексы, начинающиеся с 0, в то время как вопрос, с которым вы связываетесь, ожидает индексы, начинающиеся с 1. Следовательно, необходимо уменьшить смещение перед основным циклом while():

k--;

Answer 2

Эквивалентом того, что вы описываете в C ++, является следующий полный пример:

#include <stdio.h>
#include <string.h>
#define SIZE 1024

int main(void)
{
  int k;
  scanf("%d", &k);  // read input

  char str[SIZE] = {0};
  char generated_str[SIZE] = {0};

  for(int i = 1; i <= k; i++)
  {
    sprintf(str, "%d", i);        // convert int to string
    strcat(generated_str, str);   // append current term to the overall string
  }

  printf("%s\n", generated_str);
  printf("%c\n", generated_str[k - 1]);
  return 0;
}

Вывод:

123456789101112131415161718192021
5

Примечание. Вероятно, существует алгоритмический метод длясделайте это, хотя .. Подумайте о количестве цифр, которое имеет каждое число.Затем подумайте, как вы можете использовать операторы по модулю и делению (на 10), чтобы получить то, что вам нужно от числа.После этого вы должны пойти и повеселиться.