Dados dos números primos de cuatro dígitos, supongamos 1033 y 8179, necesitamos encontrar el camino más corto de 1033 a 8179 alterando solo un dígito a la vez, de modo que cada número que obtengamos después de cambiar un dígito sea primo. Por ejemplo, una solución es 1033, 1733, 3733, 3739, 3779, 8779, 8179
Ejemplos:
Input : 1033 8179 Output :6 Input : 1373 8017 Output : 7 Input : 1033 1033 Output : 0
La pregunta puede ser resuelta por BFS y es bastante interesante de resolver como un problema inicial para principiantes. Primero encontramos todos los números primos de 4 dígitos hasta 9999 usando la técnica de Tamiz de Eratóstenes . Y luego usando esos números formó el gráfico usando la lista de adyacencia . Después de formar la lista de adyacencia, usamos BFS simple para resolver el problema.
Implementación:
C++
// CPP program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
#include <bits/stdc++.h>
using namespace std;
class graph {
int V;
list<int>* l;
public:
graph(int V)
{
this->V = V;
l = new list<int>[V];
}
void addedge(int V1, int V2)
{
l[V1].push_back(V2);
l[V2].push_back(V1);
}
int bfs(int in1, int in2);
};
// Finding all 4 digit prime numbers
void SieveOfEratosthenes(vector<int>& v)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
int n = 9999;
bool prime[n + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Forming a vector of prime numbers
for (int p = 1000; p <= n; p++)
if (prime[p])
v.push_back(p);
}
// in1 and in2 are two vertices of graph which are
// actually indexes in pset[]
int graph::bfs(int in1, int in2)
{
int visited[V];
memset(visited, 0, sizeof(visited));
queue<int> que;
visited[in1] = 1;
que.push(in1);
list<int>::iterator i;
while (!que.empty()) {
int p = que.front();
que.pop();
for (i = l[p].begin(); i != l[p].end(); i++) {
if (!visited[*i]) {
visited[*i] = visited[p] + 1;
que.push(*i);
}
if (*i == in2) {
return visited[*i] - 1;
}
}
}
}
// Returns true if num1 and num2 differ
// by single digit.
bool compare(int num1, int num2)
{
// To compare the digits
string s1 = to_string(num1);
string s2 = to_string(num2);
int c = 0;
if (s1[0] != s2[0])
c++;
if (s1[1] != s2[1])
c++;
if (s1[2] != s2[2])
c++;
if (s1[3] != s2[3])
c++;
// If the numbers differ only by a single
// digit return true else false
return (c == 1);
}
int shortestPath(int num1, int num2)
{
// Generate all 4 digit
vector<int> pset;
SieveOfEratosthenes(pset);
// Create a graph where node numbers are indexes
// in pset[] and there is an edge between two
// nodes only if they differ by single digit.
graph g(pset.size());
for (int i = 0; i < pset.size(); i++)
for (int j = i + 1; j < pset.size(); j++)
if (compare(pset[i], pset[j]))
g.addedge(i, j);
// Since graph nodes represent indexes of numbers
// in pset[], we find indexes of num1 and num2.
int in1, in2;
for (int j = 0; j < pset.size(); j++)
if (pset[j] == num1)
in1 = j;
for (int j = 0; j < pset.size(); j++)
if (pset[j] == num2)
in2 = j;
return g.bfs(in1, in2);
}
// Driver code
int main()
{
int num1 = 1033, num2 = 8179;
cout << shortestPath(num1, num2);
return 0;
}
Java
// Java program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
import java.io.*;
import java.util.*;
class Graph {
private int V;
private LinkedList<Integer>[] l;
// Constructor
@SuppressWarnings("unchecked") Graph(int v)
{
V = v;
l = new LinkedList[v];
for (int i = 0; i < v; i++)
l[i] = new LinkedList<Integer>();
}
// Function to add an edge into the graph
void addedge(int V1, int V2)
{
l[V1].add(V2);
l[V2].add(V1);
}
// Finding all 4 digit prime numbers
static void SieveOfEratosthenes(LinkedList<Integer> v)
{
// Create a boolean array "prime[0..n]" and
// initialize all entries it as true. A value in
// prime[i] will finally be false if i is Not a
// prime, else true.
int n = 9999;
Boolean prime[] = new Boolean[n + 1];
Arrays.fill(prime, true);
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a
// prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Forming a vector of prime numbers
for (int p = 1000; p <= n; p++) {
if (prime[p])
v.add(p);
}
}
// in1 and in2 are two vertices of graph which are
// actually indexes in pset[]
int bfs(int in1, int in2)
{
int visited[] = new int[V];
Arrays.fill(visited, 0);
Queue<Integer> que = new LinkedList<Integer>();
visited[in1] = 1;
que.add(in1);
while (!que.isEmpty()) {
int p = que.poll();
for (int i : l[p]) {
if (visited[i] == 0) {
visited[i] = visited[p] + 1;
que.add(i);
}
if (i == in2) {
return visited[i] - 1;
}
}
}
return 0;
}
// Returns true if num1 and num2 differ
// by single digit.
static Boolean compare(int num1, int num2)
{
// To compare the digits
char[] s1 = (Integer.toString(num1)).toCharArray();
char[] s2 = (Integer.toString(num2)).toCharArray();
int c = 0;
if (s1[0] != s2[0])
c++;
if (s1[1] != s2[1])
c++;
if (s1[2] != s2[2])
c++;
if (s1[3] != s2[3])
c++;
// If the numbers differ only by a single
// digit return true else false
return (c == 1);
}
static int shortestPath(int num1, int num2)
{
// Generate all 4 digit
LinkedList<Integer> pset
= new LinkedList<Integer>();
SieveOfEratosthenes(pset);
// Create a graph where node numbers are indexes
// in pset[] and there is an edge between two
// nodes only if they differ by single digit.
Graph g = new Graph(pset.size());
for (int i = 0; i < pset.size(); i++) {
for (int j = i + 1; j < pset.size(); j++) {
if (compare(pset.get(i), pset.get(j)))
g.addedge(i, j);
}
}
// Since graph nodes represent indexes of numbers
// in pset[], we find indexes of num1 and num2.
int in1 = 0, in2 = 0;
for (int j = 0; j < pset.size(); j++) {
if (pset.get(j) == num1)
in1 = j;
}
for (int j = 0; j < pset.size(); j++) {
if (pset.get(j) == num2)
in2 = j;
}
return g.bfs(in1, in2);
}
// Driver code
public static void main(String[] args)
{
int num1 = 1033, num2 = 8179;
int ans = shortestPath(num1, num2);
System.out.println(ans);
}
}
// This code is contributed by cavi4762.
Python3
# Python3 program to reach a prime number # from another by changing single digits # and using only prime numbers. import queue class Graph: def __init__(self, V): self.V = V; self.l = [[] for i in range(V)] def addedge(self, V1, V2): self.l[V1].append(V2); self.l[V2].append(V1); # in1 and in2 are two vertices of graph # which are actually indexes in pset[] def bfs(self, in1, in2): visited = [0] * self.V que = queue.Queue() visited[in1] = 1 que.put(in1) while (not que.empty()): p = que.queue[0] que.get() i = 0 while i < len(self.l[p]): if (not visited[self.l[p][i]]): visited[self.l[p][i]] = visited[p] + 1 que.put(self.l[p][i]) if (self.l[p][i] == in2): return visited[self.l[p][i]] - 1 i += 1 # Returns true if num1 and num2 # differ by single digit. # Finding all 4 digit prime numbers def SieveOfEratosthenes(v): # Create a boolean array "prime[0..n]" and # initialize all entries it as true. A value # in prime[i] will finally be false if i is # Not a prime, else true. n = 9999 prime = [True] * (n + 1) p = 2 while p * p <= n: # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p for i in range(p * p, n + 1, p): prime[i] = False p += 1 # Forming a vector of prime numbers for p in range(1000, n + 1): if (prime[p]): v.append(p) def compare(num1, num2): # To compare the digits s1 = str(num1) s2 = str(num2) c = 0 if (s1[0] != s2[0]): c += 1 if (s1[1] != s2[1]): c += 1 if (s1[2] != s2[2]): c += 1 if (s1[3] != s2[3]): c += 1 # If the numbers differ only by a single # digit return true else false return (c == 1) def shortestPath(num1, num2): # Generate all 4 digit pset = [] SieveOfEratosthenes(pset) # Create a graph where node numbers # are indexes in pset[] and there is # an edge between two nodes only if # they differ by single digit. g = Graph(len(pset)) for i in range(len(pset)): for j in range(i + 1, len(pset)): if (compare(pset[i], pset[j])): g.addedge(i, j) # Since graph nodes represent indexes # of numbers in pset[], we find indexes # of num1 and num2. in1, in2 = None, None for j in range(len(pset)): if (pset[j] == num1): in1 = j for j in range(len(pset)): if (pset[j] == num2): in2 = j return g.bfs(in1, in2) # Driver code if __name__ == '__main__': num1 = 1033 num2 = 8179 print(shortestPath(num1, num2)) # This code is contributed by PranchalK
C#
// C# program to reach a prime number from
// another by changing single digits and
// using only prime numbers.
using System;
using System.Collections.Generic;
class Graph {
private int V;
private List<int>[] l;
// Constructor
Graph(int v)
{
V = v;
l = new List<int>[ v ];
for (int i = 0; i < v; i++)
l[i] = new List<int>();
}
// Function to Add an edge into the graph
void Addedge(int V1, int V2)
{
l[V1].Add(V2);
l[V2].Add(V1);
}
// Finding all 4 digit prime numbers
static void SieveOfEratosthenes(List<int> v)
{
// Create a bool array "prime[0..n]" and
// initialize all entries it as true. A value in
// prime[i] will finally be false if i is Not a
// prime, else true.
int n = 9999;
bool[] prime = new bool[n + 1];
Array.Fill(prime, true);
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a
// prime
if (prime[p] == true) {
// Update all multiples of p
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
// Forming a vector of prime numbers
for (int p = 1000; p <= n; p++) {
if (prime[p])
v.Add(p);
}
}
// in1 and in2 are two vertices of graph which are
// actually indexes in pset[]
int Bfs(int in1, int in2)
{
int[] visited = new int[V];
Array.Fill(visited, 0);
Queue<int> que = new Queue<int>();
visited[in1] = 1;
que.Enqueue(in1);
while (que.Count > 0) {
int p = que.Dequeue();
foreach(int i in l[p])
{
if (visited[i] == 0) {
visited[i] = visited[p] + 1;
que.Enqueue(i);
}
if (i == in2) {
return visited[i] - 1;
}
}
}
return 0;
}
// Returns true if num1 and num2 differ
// by single digit.
static bool Compare(int num1, int num2)
{
// To compare the digits
string s1 = num1.ToString();
string s2 = num2.ToString();
int c = 0;
if (s1[0] != s2[0])
c++;
if (s1[1] != s2[1])
c++;
if (s1[2] != s2[2])
c++;
if (s1[3] != s2[3])
c++;
// If the numbers differ only by a single
// digit return true else false
return (c == 1);
}
static int ShortestPath(int num1, int num2)
{
// Generate all 4 digit
List<int> pset = new List<int>();
SieveOfEratosthenes(pset);
// Create a graph where node numbers are indexes
// in pset[] and there is an edge between two
// nodes only if they differ by single digit.
Graph g = new Graph(pset.Count);
for (int i = 0; i < pset.Count; i++) {
for (int j = i + 1; j < pset.Count; j++) {
if (Compare(pset[i], pset[j]))
g.Addedge(i, j);
}
}
// Since graph nodes represent indexes of numbers
// in pset[], we find indexes of num1 and num2.
int in1 = 0, in2 = 0;
for (int j = 0; j < pset.Count; j++) {
if (pset[j] == num1)
in1 = j;
}
for (int j = 0; j < pset.Count; j++) {
if (pset[j] == num2)
in2 = j;
}
return g.Bfs(in1, in2);
}
// Driver code
static void Main(string[] args)
{
int num1 = 1033, num2 = 8179;
int ans = ShortestPath(num1, num2);
Console.WriteLine(ans);
}
}
// This code is contributed by cavi4762.
Producción :
6
Publicación traducida automáticamente
Artículo escrito por Shubham091996 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA