Xin ý tưởng - Bài toán tìm số trong dãy tự nhiên

Mình có 1 bài muốn tham khảo ý kiến mọi người.
Đề bài:
Viết các số tự nhiên từ 0 -> vô cùng thành 1 dãy liên tiếp. VD: 012345678910111213
Nhập số n. In ra vị trí xuất hiện của số n trong dãy.
VD: n = 45. In ra 5

Mình có làm theo kiểu chạy vòng lặp. Ném từng số vào chuỗi. Đến khi nào tìm trong chuỗi thấy thì in ra và dừng lại. Mà nó chỉ chạy ở TH n nhỏ.
Mong ý kiến đóng góp của mọi người.

   #include <iostream>
#include <iomanip>
#include <string>
#include <sstream>

using namespace std;
string s = "";
int n = 1000000000;
int k = 369;

template <typename T>
std::string genericToString(const T& t)
{
    std::ostringstream oss;
    oss << t;
    return oss.str();
}

void f(){
	for(int i=0;i<=n;i++){
		if(s.find(genericToString(k)) != -1){
			cout << s.find(genericToString(k)) + 1 << endl;
			break;
		}
		s += genericToString(i);
	}
	cout << s << endl;
}

int main(){
	f();
	return 0;
}

Tức là tìm min vị trí của r trong dãy 0123456789…?

Đúng r c.
VD: n = 45. Nếu 45 có xuất hiện trước đó thì in ra vị trí trước. còn không thì in ra vị trí số 45 cuối cùng trong day.

Chạy i = 1…m cho đến khi nhận được một dãy số liên tiếp gồm các số i chữ số (có thể bị thừa ở cả bên phải và bên trái). Đọc ra số nhỏ nhất là xong. Dự đoán là O(l^2) trung bình với l là số chữ số của mẫu để tìm.

c có thể nói rõ hơn 1 tý được k. hoặc cho mình xin 1 vd thì tốt quá.

VD: “798” do 9 > 8 nên loại i = 1, i = 2 có 2 khả năng: do 7 liền trước 8 nên lấy 98 - 1 = 97; và 79 + 1 = 80 nên nhận n = 79.

Có vẻ k ổn c ơi. với n = 798 thì đáp án phải là 149

bạn lấy length cua n, sau do chạy i lấy các giá trị từ s[i] đến s[i+length-1] nối lại so sánh với String n là đc mà, đến khi trùng thì in ra i :-??

Bác cho e xin ví dụ với.

String searching có nhiều cách giải, tham khảo nhé

1 Like
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?