Mọi người giúp em bài này với
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314… (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
Mọi người giúp em bài này với
Dãy các số tự nhiên được viết ra thành một dãy vô hạn trên đường thẳng:
1234567891011121314… (1)
Hỏi số ở vị trí thứ 1000 trong dãy trên là số nào?
####DPT ~ O(logk)
#include <stdio.h>
long pow(long n,long k){
if(k==0) return 1;
long t=pow(n,k/2);
if(k%2==0){
return t*t;
}else{
return t*t*n;
}
}
long dem(long i){
//dem tat ca cac so co i chu so
return 9*pow(10,i-1);
}
char kth(long k){
long d=0;
long i=1;
while(d+dem(i)*i < k){
// neu tat ca cac so co i chu so van nho hon k
// tang bien d len
d+=dem(i)*i;
i++;
}
long start=d+1; // vi tri dau tien cua so co i chu so
long t=(k-start)/i; // t thu tu cua so co i chu so trong day can tim
long nth=t+pow(10,i-1); // thu tu cua so can tim
long ind=(k-start) %i; // ind la chi so cua ki tu can tim trong nth
char s[30];
sprintf(s,"%ld",nth);
return s[ind];
}
int main() {
long i;
putchar(kth(1000));
return 0;
}
Chỉ có thể nói ý tưởng giúp em được không, em chẳng hiểu gì cả, bài này nhìn thế mà sao khó quá
Hàm pow chắc hiểu
hàm đếm = 10^i - 10^(i-1) là tất cả số có i chũ số:
Vd: 10…99: có 90 số
Hàm kth: mục đích của biến d là đếm tổng số chữ số trước đó của các số trước.
có 1 cách khác lâu hơn. Tinh het tat cả chữ số vào xâu s sau đó đưa ra vị trí
char s[2000];
char chuso[30];
s[0]=0;
int len=0;
int n=1;
while( len< k){
sprintf(chuso, "%d",n);
strcat(s+len,chuso);
n++;
len+= strlen(chuso);
}
chữ số cần tìm = s[k-1];
Tên topic: Nhập một dãy số.
Ví dụ: dãy 123456789101112…
=> dãy số ở đây là dãy tùy chọn do người dùng nhập hay bắt buộc phải có quy luật như trên?
Dạ thích gì thì nhập đấy
This topic was automatically closed 3 days after the last reply. New replies are no longer allowed.