Bao quanh các khối chương trình này để xác định tổng số nguyên đối ứng không chứa zero

Question

Hãy Một biểu thị tập hợp các số nguyên dương có đại diện thập phân không chứa các chữ số 0. Tổng số nghịch đảo của các yếu tố trong Một được biết đến là 23.10345.

Ví dụ: 1,2,3,4,5,6,7,8,9,11-19,21-29,31-39,41-49,51-59,61-69,71-79,81-89, 91-99,111-119, ...

Sau đó, lấy đi nghịch đảo của mỗi số và cộng tổng số.

Làm cách nào để xác minh số này?

Viết chương trình máy tính để xác minh số này.

Dưới đây là những gì tôi đã viết cho đến nay, tôi cần sự giúp đỡ bounding vấn đề này như thế này hiện đang mất quá nhiều thời gian để hoàn thành:

Mã trong Java

import java.util.*; 

public class recip 
{ 
    public static void main(String[] args) 
    { 
     int current = 0; double total = 0; 

     while(total < 23.10245) 
     { 
      if(Integer.toString(current).contains("0")) 
      { 
       current++; 
      } 
      else 
      { 
       total = total + (1/(double)current); 
       current++; 
      } 
      System.out.println("Total: " + total); 
     } 
    } 
} 

Answer 1

Đây không phải là thứ khó khăn khi tiếp cận đúng cách.

Giả sử ví dụ bạn muốn tìm tổng số nghịch đảo của tất cả các số nguyên bắt đầu (tức là các chữ số bên trái nhiều nhất) với 123 và kết thúc bằng k chữ số khác 0. Rõ ràng có 9 ^k số nguyên như vậy và nghịch đảo của mỗi số nguyên này nằm trong phạm vi 1/(124 * 10 ^k) .. 1/(123 * 10 ^k). Do đó tổng số nghịch đảo của tất cả các số nguyên này bị ràng buộc bởi (9/10) ^k/124 và (9/10) ^k/123.

Để tìm giới hạn cho tổng của tất cả các đối ứng bắt đầu bằng 123, phải thêm các giới hạn ở trên cho mỗi k> = 0. Đây là một serie hình học, do đó nó có thể được bắt nguồn rằng tổng số nghịch đảo của các số nguyên bắt đầu bằng 123 được bao bọc bởi 10 * (9/10) ^k/124 và 10 * (9/10) ^k/123.

Phương pháp tương tự có thể được áp dụng cho bất kỳ kết hợp nào của nhiều chữ số bên trái. Càng nhiều chữ số chúng tôi kiểm tra ở bên trái, kết quả càng chính xác. Đây là một thực hiện phương pháp này trong python:

def approx(t,k): 
    """Returns a lower bound and an upper bound on the sum of reciprocals of 
     positive integers starting with t not containing 0 in its decimal 
     representation. 
     k is the recursion depth of the search, i.e. we append k more digits 
     to t, before approximating the sum. A larger k gives more accurate 
     results, but takes longer.""" 
    if k == 0: 
     return 10.0/(t+1), 10.0/t 
    else: 
     if t > 0: 
      low, up = 1.0/t, 1.0/t 
     else: 
      low, up = 0, 0 
     for i in range(10*t+1, 10*t+10): 
      l,u = approx(i, k-1) 
      low += l 
      up += u 
    return low, up 

Calling khoảng (0, 8) ví dụ đưa ra thấp hơn và trên ràng buộc: 23,103447707 ... và 23,103448107 .... mà gần yêu cầu 23.10345 do OP cung cấp.

Có các phương pháp hội tụ nhanh hơn cho tổng số được đề cập, nhưng chúng đòi hỏi nhiều toán hơn. Tổng số tiền xấp xỉ tốt hơn có thể được tìm thấy here. Tổng quát vấn đề là Kempner series.

Answer 2

Đối với tất cả các giá trị của current lớn hơn một số ngưỡng N, 1.0/(double)current sẽ đủ nhỏ mà total không tăng do thêm 1.0/(double)current. Như vậy, tiêu chí chấm dứt nên một cái gì đó giống như

while(total != total + (1.0/(double)current)) 

thay vì thử nghiệm chống lại các giới hạn đó được biết đến tiên. Vòng lặp của bạn sẽ dừng lại khi current đạt đến giá trị đặc biệt này là N.

Answer 3

Tôi nghi ngờ việc truyền tới chuỗi và sau đó kiểm tra ký tự '0' là bước mất quá nhiều thời gian. Nếu bạn muốn tránh tất cả zero, có thể giúp tăng current như sau:

(Edited - nhờ Aaron McSmooth)

current++; 
for(int i = 10000000; i >= 10; i = i/10) 
{ 
    if (current % i) == 0 
    { 
     current = current + (i/10); 
    } 
} 

Đây là chưa được kiểm tra, nhưng khái niệm này phải rõ ràng: bất cứ khi nào bạn nhấn bội số của lũy thừa mười (ví dụ 300 hoặc 20000), bạn thêm công suất thấp hơn tiếp theo là 10 (trong ví dụ 10 + 1 và 1000 + 100 + 10 + 1 tương ứng) cho đến khi không còn số 0 trong số của bạn .

Thay đổi vòng kết nối while tương ứng của bạn và xem điều này có giúp cải thiện hiệu suất cho vấn đề không.

Ồ, và bạn có thể muốn hạn chế đầu ra System.out một chút. Mọi thứ mười, một hundreth hoặc 10000 lần là đủ?

Chỉnh sửa thứ hai: Sau khi ngủ, tôi nghi ngờ câu trả lời của tôi có thể hơi ngắn (đổ lỗi cho giờ muộn, nếu bạn muốn). Tôi chỉ đơn giản hy vọng rằng, một triệu lần lặp của current sẽ đưa bạn đến giải pháp và để nó ở đó, thay vì tính toán các trường hợp chỉnh sửa bằng cách sử dụng log(current) v.v.

Suy nghĩ thứ hai, tôi thấy hai vấn đề với toàn bộ vấn đề này. Một là số mục tiêu của bạn là 23.10345 là một leeeeettle để tròn cho thị hiếu của tôi. Sau khi tất cả, bạn đang thêm hàng ngàn mục như "1/17", "1/11111" và cứ thế, với các biểu diễn thập phân vô hạn và rất khó có thể thêm chúng vào chính xác 23.10345. Nếu một số chuyên gia cho toán học số nói như vậy, tốt - nhưng sau đó tôi muốn xem thuật toán mà họ đã đi đến kết luận này.

Sự cố khác liên quan đến vấn đề đầu tiên và liên quan đến giới hạn trong bộ nhớ số nhị phân trình bày các số hữu tỷ của bạn. Bạn có thể nhận được bằng cách sử dụng BigDecimals, nhưng tôi có những nghi ngờ của tôi.

Vì vậy, về cơ bản, tôi đề nghị bạn lập trình lại thuật toán số thay vì đi cho giải pháp bạo lực. Lấy làm tiếc.

Chỉnh sửa thứ ba: Vì tò mò, tôi đã viết điều này trong C++ để kiểm tra lý thuyết của mình. Nó chạy trong 6 phút và có khoảng 14,5 (khoảng 550 mio. Lần lặp). Chúng ta sẽ thấy.

Current version là

double total = 0; 
long long current = 0, currPowerCeiling = 10, iteration = 0; 
while(total < 23.01245) 
{ 
    current++; 
    iteration++; 
    if(current >= currPowerCeiling) 
     currPowerCeiling *= 10; 

    for(long long power = currPowerCeiling; power >= 10; power = power/10) 
    { 
     if((current % power) == 0) 
     { 
      current = current + (power/10); 
     } 
    } 
    total += (1.0/current); 

    if(! (iteration % 1000000)) 
     std::cout << iteration/1000000 << " Mio iterations: " << current << "\t -> " << total << std::endl; 
} 
std::cout << current << "\t" << total << std::endl; 

Tính currPowerCeiling (hoặc tuy nhiên người ta có thể gọi đây) bằng tay tiết kiệm một số log10 và pow tính toán mỗi lần lặp. Mỗi chút giúp - nhưng nó vẫn sẽ mãi mãi ...

Sửa thứ tư: Status là khoảng 66.000 mio lặp, tổng là lên đến 16,2583, thời gian chạy là vào khoảng 13 giờ. Không có vẻ tốt, Bobby S. - Tôi đề xuất một cách tiếp cận toán học hơn.

Answer 4

Làm thế nào để lưu trữ số hiện tại dưới dạng mảng byte trong đó mỗi phần tử mảng là một chữ số 0-9? Bằng cách đó, bạn có thể phát hiện các số 0 rất nhanh (so sánh các byte bằng cách sử dụng == thay vì String.contains).

Nhược điểm là bạn sẽ cần phải tự thực hiện việc gia tăng thay vì sử dụng ++. Bạn cũng sẽ cần phải đưa ra một cách để đánh dấu các chữ số "không tồn tại" để bạn không phát hiện chúng dưới dạng số không. Lưu trữ -1 cho các chữ số không tồn tại giống như một giải pháp hợp lý.

Answer 5

public class SumOfReciprocalWithoutZero { 
public static void main(String[] args) { 

    int maxSize=Integer.MAX_VALUE/10; 
    long time=-System.currentTimeMillis(); 
    BitSet b=new BitSet(maxSize); 
    setNumbersWithZeros(10,maxSize,b); 

    double sum=0.0; 
    for(int i=1;i<maxSize;i++) 
    { 
     if(!b.get(i)) 
     { 
      sum+=1.0d/(double)i; 
     } 
    } 
    time+=System.currentTimeMillis(); 
    System.out.println("Total: "+sum+"\nTimeTaken : "+time+" ms"); 


} 

static void setNumbersWithZeros(int srt,int end,BitSet b) 
{ 
     for(int j=srt;j<end;j*=10) 
     { 
      for(int i=1;i<=10;i++) 
     { 
      int num=j*i; 
      b.set(num); 
     } 
      if(j>=100) 
      setInbetween(j, b); 
     } 
} 

static void setInbetween(int strt,BitSet b) 
{ 

    int bitToSet; 
    bitToSet=strt; 
    for(int i=1;i<=10;i++) 
    { 
     int nxtInt=-1; 

    while((nxtInt=b.nextSetBit(nxtInt+1))!=strt) 
    { 
     b.set(bitToSet+nxtInt); 
    } 
    nxtInt=-1; 
    int lim=strt/10; 
    while((nxtInt=b.nextClearBit(nxtInt+1))<lim) 
    { 
     b.set(bitToSet+nxtInt); 
    } 

    bitToSet=strt*i; 

    } 
} 


} 

Đây là một thực hiện sử dụng BitSet.I tính tổng của đối ứng cho tất cả các số nguyên trong phạm vi (1-Integer.MAX_VALUE/10) .Công sum đến tối đa 13.722766931560747 .Đây là tối đa tôi có thể tính toán sử dụng BitSet kể từ khi phạm vi tối đa cho BitSet là Integer .MAX_VALUE.I cần phải phân chia nó bằng 10 và giới hạn phạm vi để tránh tràn. Nhưng có cải thiện đáng kể về tốc độ. Tôi chỉ đăng mã này trong trường hợp nó có thể cung cấp cho bạn một số ý tưởng mới để cải thiện mã của bạn.(Tăng bộ nhớ của bạn bằng cách sử dụng lập luận VM -Xmx[Size>350]m)

Output:

Total: 13.722766931560747 
TimeTaken : 60382 ms 

UPDATE:

Java Porting của một, câu trả lời đã bị xóa trước đó:

 public static void main(String[] args) { 
     long current =11; 
     double tot=1 + 1.0/2 + 1.0/3 + 1.0/4 + 1.0/5 + 1.0/6 + 1.0/7 + 1.0/8 + 1.0/9; 
     long i=0; 
     while(true) 
     { 
      current=next_current(current); 
      if(i%10000!=0) 
       System.out.println(i+" "+current+" "+tot); 
      for(int j=0;j<9;j++) 
      { 
       tot+=(1.0/current + 1.0/(current + 1) + 1.0/(current + 2) + 1.0/(current + 3) + 1.0/(current + 4) + 
          1.0/(current + 5) + 1.0/(current + 6) + 1.0/(current + 7) + 1.0/(current + 8)); 

       current += 10; 
      } 
      i++; 
     } 

    } 

    static long next_current(long n){ 

    long m=(long)Math.pow(10,(int)Math.log10(n)); 
    boolean found_zero=false; 
    while(m>=1) 
    { 
     if(found_zero) 
      n+=m; 
     else if((n/m)%10==0) 
     { 
      n=n-(n%m)+m; 
      found_zero=true; 
     } 

    m=m/10; 
    } 
    return n; 
    } 

Answer 6

Đối với số nguyên 32 bit đã ký, chương trình này sẽ không bao giờ dừng lại. Nó sẽ thực sự hội tụ về phía -2097156. Vì số hài hòa tối đa (tổng các số nguyên của số nguyên từ 1 đến N) của số nguyên 32 bit đã ký là ~14.66, vòng lặp này sẽ không bao giờ chấm dứt, ngay cả khi hiện tại quấn quanh từ 2^31 - 1 đến -2^31. Vì nghịch đảo của số nguyên 32 bit âm lớn nhất là ~ -4.6566e-10, mỗi lần trả về là 0, tổng sẽ âm. Do số lớn nhất có thể đại diện bởi số double sao cho number + + 1/2^31 == number là 2^52/2^31, bạn nhận được khoảng -2097156 làm giá trị hội tụ. Có một số điều bạn có thể làm để tăng tốc độ vòng lặp bên trong của bạn.Đầu tiên, hoạt động tốn kém nhất sẽ là System.out.println; mà phải tương tác với giao diện điều khiển trong trường hợp đó chương trình của bạn cuối cùng sẽ phải xóa bộ đệm đến bàn điều khiển (nếu có). Có những trường hợp mà điều đó có thể không thực sự xảy ra, nhưng vì bạn đang sử dụng nó để gỡ lỗi, chúng không liên quan đến câu hỏi này.

Tuy nhiên, bạn cũng dành nhiều thời gian để xác định xem một số có số không. Bạn có thể lật thử nghiệm đó xung quanh để tạo ra các dãy số nguyên như vậy trong phạm vi đó, bạn được đảm bảo không có số nguyên có chữ số bằng 0. Đó là thực sự đơn giản để làm từng bước (trong C++, nhưng đủ tầm thường để chuyển đổi sang Java):

class c_advance_to_next_non_zero_decimal 
{ 
public: 
    c_advance_to_next_non_zero_decimal(): next(0), max_set_digit_index(0) 
    { 
     std::fill_n(digits, digit_count, 0); 

     return; 
    } 

    int advance_to_next_non_zero_decimal() 
    { 
     assert((next % 10) == 0); 

     int offset= 1; 
     digits[0]+= 1; 

     for (int digit_index= 1, digit_value= 10; digit_index<=max_set_digit_index; ++digit_index, digit_value*= 10) 
     { 
      if (digits[digit_index]==0) 
      { 
       digits[digit_index]= 1; 
       offset+= digit_value; 
      } 
     } 

     next+= offset; 

     return next; 
    } 

    int advance_to_next_zero_decimal() 
    { 
     assert((next % 10)!=0); 
     assert(digits[0]==(next % 10)); 

     int offset= 10 - digits[0]; 
     digits[0]+= offset; 
     assert(digits[0]==10); 

     // propagate carries forward 
     for (int digit_index= 0; digits[digit_index]==10 && digit_index<digit_count; ++digit_index) 
     { 
      digits[digit_index]= 0; 
      digits[digit_index + 1]+= 1; 

      max_set_digit_index= max(digit_index + 1, max_set_digit_index); 
     } 

     next+= offset; 
     return next; 
    } 

private: 
    int next; 

    static const size_t digit_count= 10; // log10(2**31) 

    int max_set_digit_index; 

    int digits[digit_count]; 
}; 

gì đoạn mã trên không là để lặp qua mỗi loạt các con số như vậy mà phạm vi chỉ chứa số mà không zero. Nó hoạt động bằng cách xác định làm thế nào để đi từ N000 ... đến N111 ... và từ N111 ... đến (N + 1) 000 ..., mang (N + 1) vào 1 (0) 000 ... nếu cần thiết.

Trên máy tính xách tay của mình, tôi có thể tạo số hài hòa 2^31 - 1 trong 8.73226 giây.