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

  • Автор темы Fam
  • Дата начала
Статус
Закрыто для дальнейших ответов.
F

Fam

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

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

acorn

PHP Developer
29.08.2004
585
3
#2
это классическая олимпиадная задача кста, помню когда-то "в детстве" решал :)
но это при большом k только
а так есть разные способы.
 
F

flashkpi

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

DarkKnight

Well-Known Member
01.08.2010
653
0
#4
Чет автор замолчал.

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

DarkKnight

Well-Known Member
01.08.2010
653
0
#5
Чет оптимизация этого алгоритма меня заинтерисовала..
Пока добился вот такого, но использую строку - хоть и один раз, следовательно можно оптимизировать еще...
Завтра трезвым взглядом нужно будет взглянуть :)
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++;
}
}
 

DarkKnight

Well-Known Member
01.08.2010
653
0
#6
Реально видно спать хочу ;-)
Вот наверное оптимизированный, хотя можно еще подумать наверное ;-)
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++;
}
}
 
F

Fam

Гость
#7
Код:
#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;
}
Ну вот что то вроде этого получилось
программа не работает, смотри исправленную ниже.
 
F

Fam

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

lazybiz

Well-Known Member
03.11.2010
1 339
0
#9
Fam, это опционально, когда указано "using namespace std;"
Если "using namespace std;" не используется то .h писать необходимо.
 

lazybiz

Well-Known Member
03.11.2010
1 339
0
#10
rrrFer
Я думаю что обычный смертный не поймет как компилировать данное творение..
 

DarkKnight

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

vital

Больной Компом Детектед
29.01.2006
2 432
42
#12
ВСегда не любил С вот за это
Код:
 for(j=l=9,h=0,k=1;l<i;j*=10,h+=j,l=l+j*k)
Неужели, это может понять кто-то кроме автора?
 

DarkKnight

Well-Known Member
01.08.2010
653
0
#13
2: vital, зато как продуктивно :)))) 40-символов кода в одной строке (и 9 операций ;-))))
 

lazybiz

Well-Known Member
03.11.2010
1 339
0
#14
Предлагаю еще одно решение.

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

lazybiz

Well-Known Member
03.11.2010
1 339
0
#15
Еще немного упрощенный вариант...

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;
}
 
Статус
Закрыто для дальнейших ответов.