Задача: поиск K-ого элемента последовательности. С++

Тема в разделе "C/C++/C#", создана пользователем Fam, 10 ноя 2010.

Статус темы:
Закрыта.
  1. Fam

    Fam Гость

    Дано натуральное k. Определить k – ю цифру последовательности 12345678910111213 …, в которой выписаны подряд все натуральные числа.

    Добавлено: Дайте кто нибудь код к ней!
     
  2. acorn

    acorn PHP Developer

    Регистрация:
    29 авг 2004
    Сообщения:
    599
    Симпатии:
    3
    это классическая олимпиадная задача кста, помню когда-то "в детстве" решал :)
    но это при большом k только
    а так есть разные способы.
     
  3. flashkpi

    flashkpi Гость

    Можно сделать какой нибудь счетчик, который будет зависеть от числа К, к примеру , еси k<10, то ясно что числа однозначные, если k<90*2+9 и больше 9, то двухзначные, если k>90*2+9 и k<900*3+90*2+9*1, то трехзначные, и т.д. Примерно такой алгоритм мне кажется логичным..... Ну а вообще, решение, которое предложил rrrFer - самое простое, и мне кажется, что твоему преподу и такое покатит
     
  4. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Чет автор замолчал.

    2 Fam :
    char* - строка //Размер ее лучше выбрать как (k+1)+ strlen(itoa(k))
    memset - заполнение памяти
    strlen - длина строки
    strcat - слияние строки
    itoa - перевод из целочисленного в строку
    k+1 - индекс - т.к. индекс наверное от 1..., а в с массив от 0...
     
  5. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Чет оптимизация этого алгоритма меня заинтерисовала..
    Пока добился вот такого, но использую строку - хоть и один раз, следовательно можно оптимизировать еще...
    Завтра трезвым взглядом нужно будет взглянуть :)
    Код (C++):
        int k;
    cin >>k;
    int pos =0;
    int Mn = 1;
    int Mns =0;
    int size = 1;
    for (int i = 1; i<=k; i++)
    {
    pos+=size;
    if (pos>=k && k<=pos+size)
    {
    char buffer[8] ={0};
    itoa(i,buffer,10);
    cout<<"Result: "<<buffer[k-pos+size-1];
    break;
    }

    if (i == 9*Mn+Mns)
    {
    Mns = 9*Mn;
    Mn*=10;
    size++;
    }
    }
     
  6. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Реально видно спать хочу ;-)
    Вот наверное оптимизированный, хотя можно еще подумать наверное ;-)
    Код (C++):
    int k;
    cin >>k;
    int pos =0;
    int Mn = 1;
    int Mns =0;
    int size = 1;
    for (int i = 1; i<=k; i++)
    {
    pos+=size;
    if (pos>=k && k<=pos+size)
    {
    int Res = i;
    for (int i= pos-k, iter =10; i>1; i--)
    {
    Res = (int) Res/iter;
    }
    cout<<"Result = "<<Res%10;
    break;

    }

    if (i == 9*Mn+Mns)
    {
    Mns = 9*Mn;
    Mn*=10;
    size++;
    }
    }
     
  7. Fam

    Fam Гость

    Код (Text):
    #include<iostream.h>
    #include<conio.h>
    int main()
    {
    int k,i,a,s,j;
    a=0;
    s=0;
    j=0;
    cout<<"Vvedite cifru";
    cin>>k;
    for(i=1;i<10;i++){
    cout<<i;
    s++;
    if (a==k)
    a=i;
    }
    for(i=1;i<10;i++){
    for(j=1;j=10;j++){
    cout<<i;
    s++;
    if (a==k)
    a=i;
    cout<<j;
    s++;
    if (a==k)
    a=i;
    }
    }
    cin.get();
    return 0;
    }
    Ну вот что то вроде этого получилось
    программа не работает, смотри исправленную ниже.
     
  8. Fam

    Fam Гость

    Да прога работает
    А почему в строке #include<iostream>
    в конце нет .h вроде она пишется
    #include<iostream.h> или я ошибаюсь?
     
  9. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Fam, это опционально, когда указано "using namespace std;"
    Если "using namespace std;" не используется то .h писать необходимо.
     
  10. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    rrrFer
    Я думаю что обычный смертный не поймет как компилировать данное творение..
     
  11. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    Код как всегда на высшем уровне ;-))) Ничего лишнего и все минимизированно :)
    рФер, я на работе прошлый код просматривал, в нем ошибка(недочет, какую то операцию выходную пропустил) какая то была, не помню уже точно, хотел пока смотрел сразу отписать, но отвлекли... Щас нужно код опять просматривать заново ;-))) А твои кода я только с ручкой и листиком просматриваю ;-)) Без пометок тяжеловато иной раз бывает ;-)) Особенно ты циклы описываешь когда ;-)
     
  12. vital

    vital Больной Компом Детектед
    Команда форума Web Team

    Регистрация:
    29 янв 2006
    Сообщения:
    2.474
    Симпатии:
    27
    ВСегда не любил С вот за это
    Код (Text):
     for(j=l=9,h=0,k=1;l<i;j*=10,h+=j,l=l+j*k)
    Неужели, это может понять кто-то кроме автора?
     
  13. DarkKnight

    DarkKnight Well-Known Member
    C\C++ Team

    Регистрация:
    1 авг 2010
    Сообщения:
    653
    Симпатии:
    0
    2: vital, зато как продуктивно :)))) 40-символов кода в одной строке (и 9 операций ;-))))
     
  14. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Предлагаю еще одно решение.

    Код (C++):
    #include <iostream.h>

    int main( void )
    {
    int     c, d, k, j, n, z;

    cout << "Enter k: "; cin >> k;

    c = n = 0;
    do {
    n++;
    for ( d = 1, j = n; j /= 10; d++ );
    c += d;
    } while ( c < k );
    for ( z = c - k; z--; n /= 10 );

    cout << "Result: " << n % 10 << endl;
    return 0;
    }
     
  15. lazybiz

    lazybiz Well-Known Member
    C\C++ Team

    Регистрация:
    3 ноя 2010
    Сообщения:
    1.344
    Симпатии:
    0
    Еще немного упрощенный вариант...

    Код (C++):
    #include <iostream.h>

    int main( void )
    {
    int c, k, j, n;

    cin >> k;

    c = n = 0;
    do {
    for ( n++, c++, j = n; j /= 10; c++ );
    } while ( c < k );
    for ( c -= k; c--; n /= 10 );

    cout << "Result: " << n % 10 << endl;
    cin.get();
    return 0;
    }
     
Загрузка...
Похожие Темы - Задача поиск ого
  1. Янчик
    Ответов:
    0
    Просмотров:
    490
  2. TrishaRay
    Ответов:
    1
    Просмотров:
    783
  3. elzim
    Ответов:
    0
    Просмотров:
    932
  4. ShaoKahn
    Ответов:
    0
    Просмотров:
    1.128
  5. eremin-sanek
    Ответов:
    3
    Просмотров:
    1.107
Статус темы:
Закрыта.

Поделиться этой страницей