01/10/2018, 12:30
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;
}
Bài liên quan
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é
en.wikipedia.org
String-searching algorithm
In computer science, string-searching algorithms, sometimes called string-matching algorithms, are an important class of string algorithms that try to find a place where one or several strings (also called patterns) are found within a larger string or text. Let Σ be an alphabet (finite set). The most basic example of string searching is where both the pattern and searched text are arrays of elements of Σ. The Σ may be a usual human alphabet (for example, the letters A through Z in the Latin alph...