SPOJ PPATH, Chuyển đổi số nguyên 4 chữ số thành số 4 chữ số khác

Question

Trong bài toán SPOJ PPATH chúng tôi có hai số nguyên tố 4 chữ số và chúng tôi phải chuyển đổi, trong các bước ít nhất có thể. bằng cách thay đổi một chữ số tại một thời điểm và tại mỗi bước, số phải là số nguyên tố. Chúng ta phải xuất ra 'IMPOSSIBLE' nếu các số nguyên tố không thể chuyển đổi theo kiểu thời trang đã nói. Tuy nhiên, các giải pháp cho vấn đề trong đó trường hợp không thể thậm chí không được coi là đã được chấp nhận, dẫn đến một giả thuyết rằng mọi số nguyên bốn chữ số có thể được chuyển đổi thành bất kỳ số nguyên bốn chữ số khác theo cách được chỉ định. Tôi không thể chứng minh điều đó. Có đúng không? Làm thế nào chúng ta có thể chứng minh nó một cách chính thức? Ngoài ra, có một kết quả chung cho các số nguyên tố n chữ số không?

Answer 1

Đối với số có bốn chữ số, điều này có thể được xác minh thấu đáo thông qua một chương trình nhưng đối với chữ số n, chúng tôi sẽ phải chứng minh về mặt lý thuyết.

Answer 2

Vì vậy, bạn có đồ thị vô hướng với các đỉnh như một số có 4 chữ số chính và một cạnh nối hai số khác nhau trong 1 chữ số. Bạn được yêu cầu tìm đường đi gần nhất từ ​​đỉnh này đến đỉnh khác. Kết quả IMPOSSIBLE sẽ được sản xuất nếu bạn sẽ không thể tìm thấy con đường như vậy. Điều đó có nghĩa là biểu đồ có nhiều thành phần được kết nối. Nếu bạn chứng minh rằng biểu đồ này có một thành phần được kết nối, nó sẽ đảm bảo sự tồn tại của đường dẫn.

Tôi không biết làm thế nào để chứng minh nó một cách chính thức nhưng nó rất dễ dàng để kiểm tra nếu đồ thị mô tả ở trên chỉ có một thành phần kết nối. Bạn có thể viết một thuật toán và kết quả của nó có thể được hiểu là một bằng chứng cho một trường hợp cụ thể của đồ thị 4 chữ số.