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

[Fam]

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

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

 

[acorn]

это классическая олимпиадная задача кста, помню когда-то "в детстве" решал
но это при большом k только
а так есть разные способы.

 

[flashkpi]

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

 

[DarkKnight]

Чет автор замолчал.

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

 

[DarkKnight]

Чет оптимизация этого алгоритма меня заинтерисовала..
Пока добился вот такого, но использую строку - хоть и один раз, следовательно можно оптимизировать еще...
Завтра трезвым взглядом нужно будет взглянуть

	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++;
}
}

 

[DarkKnight]

Реально видно спать хочу ;-)
Вот наверное оптимизированный, хотя можно еще подумать наверное ;-)

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++;
}
}

 

[Fam]

#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;
}

Ну вот что то вроде этого получилось
программа не работает, смотри исправленную ниже.

 

[Fam]

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

 

[lazybiz]

Fam, это опционально, когда указано "using namespace std;"
Если "using namespace std;" не используется то .h писать необходимо.

 

[lazybiz]

rrrFer
Я думаю что обычный смертный не поймет как компилировать данное творение..

 

[DarkKnight]

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

 

[vital]

ВСегда не любил С вот за это

 for(j=l=9,h=0,k=1;l<i;j*=10,h+=j,l=l+j*k)

Неужели, это может понять кто-то кроме автора?

 

[DarkKnight]

2: vital, зато как продуктивно ))) 40-символов кода в одной строке (и 9 операций ;-))))

 

[lazybiz]

Предлагаю еще одно решение.

#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;
}

 

[lazybiz]

Еще немного упрощенный вариант...

#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;
}