Số lượng cử tri tối thiểu, được chia hai nửa số

Question

Một trong những cựu sinh viên của tôi đã gửi cho tôi một thông điệp về câu hỏi phỏng vấn này mà anh ta nhận được khi nộp đơn xin việc làm Nhà phát triển Junior.

Có hai ứng cử viên tranh cử tổng thống trong cuộc bầu cử lớp học giả. Với hai phần trăm cử tri, hãy tìm ra số lượng cử tri ít nhất có thể trong lớp học.

Ví dụ:

Input: 50.00,50.00
Output: 2

Input: 25.00,75.00
Output: 4

Input: 53,23, 46,77
Output: 124 // Giá trị đầu tiên, 1138 là sai. Nhờ Loïc cho giá trị đúng

Lưu ý: Tổng số tỷ lệ đầu vào luôn 100.00%, hai chữ số thập phân

Ví dụ cuối cùng đã cho tôi gãi đầu của tôi. Đây là lần đầu tiên tôi nghe về vấn đề này, và tôi rất lo lắng về cách giải quyết vấn đề này.

EDIT: Tôi đã gọi cho sinh viên của tôi về vấn đề này và nói với tôi rằng anh ấy không chắc chắn về giá trị cuối cùng. Ông nói, và tôi trích dẫn, "Đó là một số lượng lớn vô lý": (xin lỗi! Tôi nên nghiên cứu thêm trước khi đăng nó trực tuyến ~ Tôi đoán rằng 9.797 là đầu ra trên ví dụ cuối cùng mặc dù ..

Answer 1

Bạn có thể tính toán các giá trị này bằng cách sử dụng best rational approximations của tỷ lệ cử tri. Wikipedia mô tả cách lấy các giá trị này từ continued fraction (có thể tính toán chúng bằng cách sử dụng euclidean algorithm). Kết quả mong muốn là xấp xỉ đầu tiên trong khoảng 0,005% giá trị kỳ vọng.

Dưới đây là một ví dụ với 53,23%:

10000 = 1 * 5323 + 4677 
5323 = 1 * 4677 + 646 
4677 = 7 * 646 + 155 
646 = 4 * 155 + 26 
155 = 5 * 26 + 25 
26 = 1 * 25 + 1 
25 = 25* 1 + 0 

Approximations: 
1: 1/1 
-> 1 = 100% 
2: 1/(1 + 1/1) 
-> 1/2 = 50% 
2.5: 1/(1 + 1/(1 + 1/6)) 
-> 7/1 = 53.75% 
3: 1/(1 + 1/(1 + 1/7)) 
-> 8/15 = 53.33% 
3.5: 1/(1 + 1/(1 + 1/(7 + 1/3))) 
-> 25/47 = 53.19% 
4: 1/(1 + 1/(1 + 1/(7 + 1/4))) 
-> 33/62 = 53.23% 

Lý do chúng tôi có giá trị thêm trước thứ 3 và convergents thứ 4 là điều kiện cuối cùng của họ (7 và 4 tương ứng) là lớn hơn 1, vì vậy chúng tôi phải kiểm tra sự xấp xỉ với thuật ngữ cuối cùng bị giảm đi.

Kết quả mong muốn là mẫu số của giá trị đầu tiên làm tròn với giá trị mong muốn, mà trong bình này là 62.

Triển khai mẫu Ruby có sẵn here (sử dụng công thức từ trang Wikipedia here, do đó có vẻ hơi khác so với ví dụ trên).

Answer 2

. Trước tiên, bạn có thể nhận thấy rằng một giải pháp tầm thường là phải có 10.000 cử tri Bây giờ chúng ta hãy cố gắng tìm một cái gì đó thấp hơn

For each value of N starting à 1 
    For Each value of i starting à 1 
    If i/N = 46.77 
     return N 

Luôn chọn tối thiểu của hai tỷ lệ phần trăm để được nhanh hơn

Hoặc nhanh hơn..:

For each value of N starting à 1 
    i = floor(N*46.77/100) 
    For j = i or i+1 
    If round(j/N) = 46.77 and round((N-j)/N) = 53.23 
     return N 

---

Đối với ví dụ thứ ba:

• 605/1138 = .5316344464
• (1138-605)/1138 = .4683655536

nhưng

• 606/1138 = .5325131810
• (1138-606)/1138 = .4674868190

Nó không thể 1138 ...

Nhưng 62 đang làm việc:

• 33/62 = .5322580645
• (62-33)/62 =.4677419355

Làm tròn nó mang lại cho bạn những giá trị tốt.

Answer 3

(Sau khi một số chỉnh sửa mở rộng :)

Nếu bạn chỉ có 2 cử tri, sau đó bạn chỉ có thể tạo ra các tỷ lệ phần trăm sau cho thí sinh A và B:

0+100, 100+0, or 50+50 

Nếu bạn có 3 cử tri, sau đó bạn có

0+100, 100+0, 33.33+66.67, 66.67+33.33 [notice the rounding] 

Vì vậy, đây là một vấn đề thú vị về phân số.

Nếu bạn có thể kiếm được 25% thì bạn phải có ít nhất 4 người (vì vậy bạn có thể làm 1/4, vì 1/2 và 1/3 sẽ không cắt nó). Bạn có thể làm điều đó với nhiều hơn (tức là 2/8 = 25%) nhưng vấn đề yêu cầu ít nhất.

Tuy nhiên, phần thú vị hơn yêu cầu số lượng nhiều hơn 1 trong tử số:

2/5 = 40% 

Vì bạn không thể có được điều đó với bất cứ điều gì nhưng 2 hoặc nhiều hơn trong tử số (1/x sẽ không bao giờ cắt nó).

Bạn có thể so sánh ở mỗi bước và tăng tử số hoặc mẫu số, hiệu quả hơn nhiều so với lặp qua toàn bộ không gian mẫu cho j và sau đó tăng i;

tức là nếu bạn có tỷ lệ phần trăm 3%, hãy kiểm tra tất cả các giải pháp theo cách thức lên 96/99, 97/99, 98/99 trước khi lên tới x/100 là phí thời gian. Thay vào đó, bạn có thể tăng tử số hoặc mẫu số dựa trên khả năng đoán hiện tại của bạn đang làm (lớn hơn hoặc ít hơn) như vậy

int max = 5000; //we only need to go half-way at most. 

public int minVoters (double onePercentage) { 

    double checkPercentage = onePercentage; 
    if (onePercentage > 50.0) 
     checkPercentage = 100-onePercentage; //get the smaller percentage value 

    double i=1; 
    double j=1; //arguments of Math.round must be double or float 
    double temp = 0; 

    while (j<max || i<max-1) { //we can go all the way to 4999/5000 for the lesser value 

     temp = (i/j)*100; 
     temp = Math.round(temp); 
     temp = temp/100; 

     if (temp == checkPercentage) 
      return j; 

     else if (temp > checkPercentage) //we passed up our value and need to increase the denominator 
      j++; 

     else if (temp < checkPercentage) //we are too low and increase the numerator 
      i++; 
    } 

    return 0; //no such solution 
} 

Step-khôn ngoan ví dụ cho việc tìm kiếm mẫu số đó có thể mang lại 55%

55/100 = 11/20 

    100-55 = 45 = 9/20 (checkPercentage will be 45.0) 


1/1 100.0% 
1/2 50.00% 
1/3 33.33% 
2/3 66.67% 
2/4 50.00% 
2/5 40.00% 
3/5 60.00% 
3/6 50.00% 
3/7 42.86% (too low, increase numerator) 
4/7 57.14% (too high, increase denominator) 
4/8 50.00% 
4/9 44.44% 
5/9 55.56% 
5/10 50.00% 
5/11 45.45% 
6/11 54.54% 
6/12 50.00% 
6/13 46.15% 
6/14 42.86% 
7/14 50.00% 
7/15 46.67% 
7/16 43.75% 
8/16 50.00% 
8/17 47.06% 
8/19 42.11% 
9/19 47.37% 
9/20 45.00% <-bingo 

những điều tốt đẹp về phương pháp này là nó sẽ chỉ mất (i + j) bước nơi i là tử số và j là mẫu số.

Answer 4

Tôi không thể thấy sự liên quan của câu hỏi này với tư cách là nhà phát triển cơ sở.

Answer 5

Sau đó câu trả lời nhảy vào đầu tôi là một cách tiếp cận bạo lực hơn. Có thể có tối đa 5001 câu trả lời duy nhất vì có 5001 số duy nhất trong khoảng từ 00,00 đến 50,00. Do đó, tại sao không tạo và lưu bảng tra cứu. Rõ ràng, sẽ không có 5001 câu trả lời duy nhất vì một số câu trả lời sẽ được lặp lại. Vấn đề là, chỉ có 5001 phân số hợp lệ bởi vì chúng tôi làm tròn đến hai chữ số.

int[] minPossible = new int[5001]; 
int numSolutionsFound = 0; 
N = 2; 
while(numSolutionsFound < 5001) { 
    for(int i = 0 ; i <= N/2 ; i++) { 
    //compute i/N 
    //see if the corresponding table entry is set 
    //if not write N there and increment numSolutionsFound 
    } 
    N++; 
} 

//Save answer here 

Bây giờ, giải pháp đơn thuần chỉ là bảng tra cứu.

FWIW Tôi nhận thấy giải pháp euclide là "chính xác". Nhưng tôi KHÔNG BAO GIỜ đến với cuộc phỏng vấn giữa đó. Tuy nhiên, tôi biết điều gì đó như thế là có thể - nhưng tôi sẽ không thể đánh bại nó ngay tại chỗ.