Tổng số các ước số lẻ lớn nhất của số n đầu tiên

Question

Tôi đã làm việc trên bộ mã hóa gần đây và tôi tình cờ gặp phải câu hỏi này mà tôi không thể hiểu được. Câu hỏi là tìm F (n) = f (1) + f (2) + .... + f (n) cho một "n" nhất định sao cho f (n) là ước số lẻ lớn nhất cho n. Có nhiều giải pháp nhỏ cho câu trả lời; tuy nhiên, tôi thấy giải pháp này rất hấp dẫn.

int compute(n) { 
if(n==0) return 0; 
long k = (n+1)/2; 
return k*k + compute(n/2); 
} 

Tuy nhiên, tôi hoàn toàn không hiểu cách lấy mối quan hệ đệ quy từ câu lệnh vấn đề như thế này. Ai đó có thể giúp đỡ?

Answer 1

Tôi tin rằng họ đang cố gắng sử dụng các sự kiện sau đây:

• f (2k + 1) = 2k + 1, tức là số chia lẻ lớn nhất của một số lẻ là số chinh no.
• f (2k) = f (k). tức là ước số lẻ lớn nhất của một số chẵn là 2m giống như ước số lẻ lớn nhất của số m.
• Tổng số k lẻ đầu tiên bằng k^2.

Bây giờ chia {1,2, ..., 2m + 1} thành {1,3,5,7, ...} và {2,4,6, ..., 2m} và cố gắng áp dụng các sự kiện trên.

Answer 2

Tôi không thể xem thuật toán đó có thể hoạt động như thế nào cho sự cố bạn đã mô tả. (Tôi sẽ giả định rằng "N" và "n" tham chiếu đến cùng một biến).

Với n = 12.

Các ước số lẻ lớn nhất là 3 (những người khác là 1, 2, 4, 6 & 12)

F (12) là do f (1) + f (2) + f (3) hoặc 1 + 1 + 3 hoặc 5.

Sử dụng thuật toán này:

k = (12 + 1)/2 hoặc 6

và chúng tôi quay trở lại 6 * 6 + f (6), hoặc 36 + một số không được goin g là tiêu cực 31.

Answer 3

nếu điều này là Java, tôi muốn nói:

import java.util.*; 
int sum_largest_odd_factors (int n){ 
     ArrayList<Integer> array = new ArrayList();//poorly named, I know 
     array.add(1); 
     for(int j = 2; j <= n; j++){ 
      array.add(greatestOddFactor(j)); 
     } 
     int sum = 0; 
     for(int i = 0; i < array.size(); i++){ 
      sum += array.get(i); 
     } 
     return sum; 
} 
int greatestOddFactor(int n){ 
     int greatestOdd = 1; 
     for(int i = n-((n%2)+1); i >= 1; i-=2){ 
      //i: starts at n if odd or n-1 if even 
      if(n%i == 0){ 
       greatestOdd = i; 
       break; 
       //stop when reach first odd factor b/c it's the largest 
      } 
     } 
     return greatestOdd; 
} 

Đây là thừa nhận tẻ nhạt và có thể là một O (n^2) hoạt động, nhưng sẽ làm việc mọi lúc. Tôi sẽ để nó cho bạn dịch sang C++ như Java và J là những ngôn ngữ duy nhất tôi có thể làm việc với (và thậm chí là ở mức thấp). Tôi tò mò về những thuật toán khéo léo mà người khác có thể đưa ra để làm điều này nhanh hơn nhiều.

Answer 4

u NẾU đang tìm kiếm tổng hợp của tất cả các ước lẻ cho đến n ..

Sum của tất cả các ước lẻ của số n đầu tiên

...

for(long long int i=1;i<=r;i=i+2) 
{ 
    sum1=sum1+i*(r/i); 
} 

để tổng hợp của tất cả các ước số trong một phạm vi từ l đến r

for(long long int i=1;i<=r;i=i+2) 
{ 
    sum1=sum1+i*(r/i); 
} 

for(long long int i=1;i<l;i=i+2) 
{ 
    sum2=sum2+i*((l-1)/i); 
} 

ans=sum1-sum2;;; 

CẢM ƠN !!

Answer 5

Bạn có thể sử dụng cách tiếp cận năng động cũng sử dụng các không gian phụ trợ

int sum=0; 
int a[n+1]; 
for(int i=1;i<=n;i++){ 
    if(i%2!=0) 
    a[i] = i; 
    else 
    a[i] = a[i/2]; 
} 
for(int i=1;i<=n;i++){ 
    sum+=a[i]; 
} 
cout<<sum; 

Như khi số là số lẻ thì số sẽ là những ước lẻ lớn nhất và a [i] sẽ lưu trữ giá trị của nó và khi số này thậm chí sau đó một [số/2] sẽ được lưu trữ trong [i] bởi vì cho số chẵn lẻ, ước số lẻ lớn nhất của số/2 sẽ là ước số lẻ lớn nhất của số.

Nó cũng có thể được giải quyết bằng cách sử dụng ba trường hợp khi số lẻ sau đó thêm số khác nếu số là lũy thừa của 2 rồi thêm 1 nếu số thậm chí còn trừ lũy thừa 2 chia cho 2 cho đến khi bạn lẻ và thêm lẻ để tổng hợp.