Cầu vượt qua câu đố

Question

Bốn người đàn ông phải băng qua một cây cầu vào ban đêm. Bất kỳ bên nào vượt qua, hoặc một hoặc hai người đàn ông, phải mang theo đèn pin với họ. Đèn pin phải được đi qua lại; nó không thể được ném, vv Mỗi người đàn ông đi với tốc độ khác. Một mất 1 phút để vượt qua, thêm 2 phút nữa, 5 phút nữa và 10 phút cuối cùng. Nếu hai người đàn ông băng qua nhau, họ phải đi bộ với tốc độ của người chậm hơn. Không có thủ thuật - những người đàn ông đều bắt đầu ở cùng một phía, đèn pin không thể tỏa sáng một khoảng cách dài, không ai có thể được mang theo, v.v.

Và câu hỏi là tất cả những gì họ có thể vượt qua nhanh nhất. Tôi về cơ bản đang tìm kiếm một số cách tiếp cận chung cho các loại vấn đề. Tôi đã được bạn của tôi nói, rằng điều này có thể được giải quyết bằng chuỗi Fibonacci, nhưng giải pháp không hoạt động cho tất cả.

Xin lưu ý đây không phải là công việc nhà.

Answer 1

Có an entire PDF (alternate link) giải quyết trường hợp chung của vấn đề này (bằng chứng chính thức).

Answer 2

17 phút - đây là câu hỏi MS cổ điển.

1,2 => 2 minutes passed. 
1 retuns => 3 minutes passed. 
5,10 => 13 minutes passed. 
2 returns => 15 minutes passed. 
1,2 => 17 minute passed. 

Nói chung, vấn đề lớn nhất/người chậm nhất phải luôn được đặt cùng nhau và đủ các chuyến đi nhanh nhất để có thể mang ánh sáng trở lại mỗi lần mà không sử dụng tài nguyên chậm.

Answer 3

17 - một câu hỏi rất phổ biến

-> 1-2 = 2
< - 2 = 2
-> 5,10 = 10 (không ai trong số họ đã trở lại)
< - 1 = 1
-> 1,2 = 2

tất cả ở phía bên kia
tổng = 2 + 2 + 10 + 1 + 2 = 17

usuall y người nhận được nó là 19 trong lần thử đầu tiên

Answer 4

Tôi sẽ giải quyết vấn đề này bằng cách đặt quảng cáo việc làm giả trên Dice.com và sau đó đặt câu hỏi này trong các cuộc phỏng vấn cho đến khi có ai đó làm đúng.

Answer 5

Tìm kiếm đầy đủ tất cả các khả năng rất đơn giản với không gian có vấn đề nhỏ như vậy. Chiều rộng hoặc chiều sâu đầu tiên sẽ hoạt động. Nó là một vấn đề CS đơn giản.

tôi thích truyền giáo và các vấn đề ăn thịt người bản thân mình

Answer 6

Theo Wikipedia

Các câu đố được biết là đã xuất hiện vào đầu năm 1981, trong cuốn sách Siêu Chiến lược Đối với câu đố và trò chơi. Trong phiên bản này của câu đố, A, B, C và D mất 5, 10, 20 và 25 phút, tương ứng, để vượt qua và giới hạn thời gian là 60 phút

Câu hỏi này được phổ biến rộng rãi sau khi xuất hiện trong cuốn sách "Bạn sẽ di chuyển núi Phú Sĩ như thế nào?"

câu hỏi có thể được khái quát hóa cho N người với thời gian cá nhân khác nhau được thực hiện để băng qua cây cầu.

Chương trình dưới đây hoạt động cho N chung không có người và thời gian của họ.

class Program 
{ 
    public static int TotalTime(List<int> band, int n) 
    { 
     if (n < 3) 
     { 
      return band[n - 1]; 
     } 
     else if (n == 3) 
     { 
      return band[0] + band[1] + band[2]; 
     } 
     else 
     { 
      int temp1 = band[n - 1] + band[0] + band[n - 2] + band[0]; 
      int temp2 = band[1] + band[0] + band[n - 1] + band[1]; 

      if (temp1 < temp2) 
      { 
       return temp1 + TotalTime(band, n - 2); 
      } 
      else if (temp2 < temp1) 
      { 
       return temp2 + TotalTime(band, n - 2); 
      } 
      else 
      { 
       return temp2 + TotalTime(band, n - 2); 
      } 
     } 
    } 

    static void Main(string[] args) 
    { 
     // change the no of people crossing the bridge 
     // add or remove corresponding time to the list 
     int n = 4; 

     List<int> band = new List<int>() { 1, 2, 5, 10 }; 

     band.Sort(); 

     Console.WriteLine("The total time taken to cross the bridge is: " + Program.TotalTime(band, n)); 
     Console.ReadLine(); 
    } 
} 

OUTPUT:

Tổng thời gian thực hiện để qua cầu là: 17

Đối,

int n = 5; 
List<int> band = new List<int>() { 1, 2, 5, 10, 12 }; 

OUTPUT:

Tổng thời gian thực hiện để vượt qua cầu là: 25

.210

Đối,

int n = 4; 
List<int> band = new List<int>() { 5, 10, 20, 25 }; 

OUTPUT Tổng thời gian thực hiện để qua cầu là: 60

Answer 7

tôi vạch ra các giải pháp khả thi đại số và bước ra với thời gian nhanh nhất. và gán đại số với danh sách A, B, C, D trong đó A là nhỏ nhất và D là lớn nhất công thức trong thời gian ngắn nhất là B + A + D + B + B hoặc 3B + A + D hoặc trong các thuật ngữ dài dòng, tổng số lần nhanh thứ hai 3 và cộng với nhanh nhất và chậm nhất.

xem chương trình cũng có câu hỏi về các mục tăng lên. Mặc dù tôi đã không đi qua nó, nhưng tôi đoán công thức vẫn được áp dụng, chỉ cần thêm cho đến khi tất cả các mục với mục thứ hai lần 3 và tổng của tất cả mọi thứ trừ 2 lần chậm nhất. ví dụ: kể từ 4 mục là 3 x giây + đầu tiên và thứ tư. thì 5 mục là 3 x giây + thứ nhất, thứ ba và thứ năm. muốn kiểm tra điều này bằng chương trình.

Tôi cũng chỉ xem pdf được chia sẻ ở trên, vì vậy, đối với nhiều mục, nó là tổng của 3 x giây + nhanh nhất + tổng chậm nhất của mỗi cặp tiếp theo.

xem xét các bước cho giải pháp được tối ưu hóa, ý tưởng là -right - cho hai mục ở bên phải nhanh nhất là nhanh nhất thứ nhất và thứ hai, -left - sau đó cộng lại nhanh nhất cho một mục là mục nhanh nhất -right - mang lại 2 mục chậm nhất, mục này sẽ chỉ chiếm mục chậm nhất và bỏ qua giây chậm nhất thứ hai. -left - mục nhanh thứ 2. -final right - nhanh thứ nhất và thứ hai một lần nữa

vì vậy tổng hợp lại nhanh hơn lần thứ 2 đi 3 lần, nhanh nhất một lần và chậm nhất đi chậm nhất 2 giây.

Answer 8

Một thuật toán đơn giản là: giả 'N' là số lượng người đã có thể vượt qua cùng lúc và một người đã qua lại mang ngọn đuốc

1. Khi di chuyển người từ bên này đầu tiên sở thích bên thứ hai nên được cung cấp cho những người đi bộ chậm nhất 'N'
2. Luôn sử dụng khung tập đi nhanh nhất để lấy ngọn đuốc từ bên thứ hai sang bên thứ nhất
3. Khi di chuyển người từ bên thứ nhất sang bên thứ hai, xem xét ai sẽ mang lại ngọn đuốc trong bước tiếp theo.Nếu tốc độ của chân vịt ở bước tiếp theo sẽ bằng với khung đi bộ nhanh nhất, trong số những người đi bộ chậm nhất 'N', trong bước hiện tại thì thay vì chọn 'N' walker chậm nhất, như được cho trong '1', chọn 'N 'người đi bộ nhanh nhất

Dưới đây là một kịch bản mẫu python mà thực hiện điều này: https://github.com/meowbowgrr/puzzles/blob/master/bridgentorch.py

Answer 9

đây là phản ứng trong ruby:

@values = [1, 2, 5, 10] 
# @values = [1, 2, 5, 10, 20, 25, 30, 35, 40] 
@values.sort! 
@position = @values.map { |v| :first } 
@total = 0 

def send_people(first, second) 
    first_time = @values[first] 
    second_time = @values[second] 

    @position[first] = :second 
    @position[second] = :second 

    p "crossing #{first_time} and #{second_time}" 

    first_time > second_time ? first_time : second_time 
end 

def send_lowest 
    value = nil 
    @values.each_with_index do |v, i| 
    if @position[i] == :second 
     value = v 
     @position[i] = :first 
     break 
    end 
    end 

    p "return #{value}" 
    return value 
end 


def highest_two 
    first = nil 
    second = nil 

    first_arr = @position - [:second] 

    if (first_arr.length % 2) == 0 
    @values.each_with_index do |v, i| 
     if @position[i] == :first 
     first = i unless first 
     second = i if !second && i != first 
     end 

     break if first && second 
    end 
    else 
    @values.reverse.each_with_index do |v, i| 
     real_index = @values.length - i - 1 
     if @position[real_index] == :first 
     first = real_index unless first 
     second = real_index if !second && real_index != first 
     end 

     break if first && second 
    end 
    end 

    return first, second 
end 

#we first send the first two 
@total += send_people(0, 1) 
#then we get the lowest one from there 
@total += send_lowest 
#we loop through the rest with highest 2 always being sent 
while @position.include?(:first) 
    first, second = highest_two 
    @total += send_people(first, second) 
    @total += send_lowest if @position.include?(:first) 
end 

p "Total time: #{@total}" 

Answer 10

một thực hiện của ruby ​​lấy cảm hứng từ @ roc-Khalil' giải pháp

s

@values = [1,2,5,10] 
# @values = [1,2,5,10,20,25] 
@left = @values.sort 
@right = [] 
@total_time = 0 

def trace(moving) 
    puts moving 
    puts "State: #{@left} #{@right}" 
    puts "Time: #{@total_time}" 
    puts "-------------------------" 
end 

# move right the fastest two 
def move_fastest_right! 
    fastest_two = @left.shift(2) 
    @right = @right + fastest_two 
    @right = @right.sort 
    @total_time += fastest_two.max 
    trace "Moving right: #{fastest_two}" 
end 

# move left the fastest runner 
def move_fastest_left! 
    fastest_one = @right.shift 
    @left << fastest_one 
    @left.sort! 
    @total_time += fastest_one 
    trace "Moving left: #{fastest_one}" 
end 

# move right the slowest two 
def move_slowest_right! 
    slowest_two = @left.pop(2) 
    @right = @right + slowest_two 
    @right = @right.sort 
    @total_time += slowest_two.max 
    trace "Moving right: #{slowest_two}" 
end 

def iterate! 
    move_fastest_right! 
    return if @left.length == 0 

    move_fastest_left! 
    move_slowest_right! 
    return if @left.length == 0 

    move_fastest_left! 
end 

puts "State: #{@left} #{@right}" 
puts "-------------------------" 
while @left.length > 0 
    iterate! 
end 

Output:

State: [1, 2, 5, 10] [] 
------------------------- 
Moving right: [1, 2] 
State: [5, 10] [1, 2] 
Time: 2 
------------------------- 
Moving left: 1 
State: [1, 5, 10] [2] 
Time: 3 
------------------------- 
Moving right: [5, 10] 
State: [1] [2, 5, 10] 
Time: 13 
------------------------- 
Moving left: 2 
State: [1, 2] [5, 10] 
Time: 15 
------------------------- 
Moving right: [1, 2] 
State: [] [1, 2, 5, 10] 
Time: 17 
-------------------------