Ulam-Zahlenfolge
Bei einer positiven Ganzzahl n besteht die Aufgabe darin , die n - te Zahl der Ulam - Zahlenfolge zu drucken dann ist für jedes n > 2 U n als kleinste positive ganze Zahl größer als U n-1 definiert , die auf genau eine Weise als Summe zweier unterschiedlicher früherer Terme der Folge ausgedrückt werden kann. Beispielsweise,
- 3 ist eine Ulam-Zahl, da sie als Summe zweier unterschiedlicher früherer Terme auf genau eine Weise ausgedrückt werden kann
(z. B. 1 + 2). - 4 ist auch eine Ulam-Zahl. Anders als ( 1 + 3) können wir 4 als ( 2 + 2 ) ausdrücken, aber in (2 + 2) sind Terme nicht verschieden. Also haben wir nur einen Weg
- 5 kann als Summe zweier unterschiedlicher früherer Terme der Folge auf zwei Arten
als ( 1 + 4 ) und ( 2 + 3) ausgedrückt werden, also ist 5 keine Ulam-Zahl
Die ersten paar Terme der Ulam-Zahlenfolge sind-
1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, 48, 53, 57, 62, 69, 72, 77, 82, 87, 97, 99, 102
Beispiele:
Input : 5 Output : 6 Input : 9 Output : 16
Eine einfache Lösung , um den n -ten Term der Ulam-Zahlenfolge zu drucken, besteht darin, die gesamte ulam-Folge bis n zu generieren und den n -ten Term zu drucken, da wir den n -ten Term nicht direkt berechnen können.
Ansatz zur Generierung der ulam-Nummernfolge:
- As, Wir haben die ersten beiden Terme der Folge als U 1 =1 und U 2 =2. Wir können unsere Suche bei i = 3 für die nächste Ulam-Nummer beginnen.
- Durchlaufen Sie für jeden Wert von 'i' die früheren Terme der Sequenz mit zwei Schleifen und prüfen Sie, ob wir beim Hinzufügen von zwei verschiedenen Termen der Sequenz die Summe als i auf genau eine Weise erhalten können oder nicht
- Wenn ja, dann ist 'i' die nächste Ulam-Nummer, speichern Sie sie. und suchen Sie dann nach der nächsten Ulam-Nummer
- Wenn nicht, erhöhen Sie 'i' und wiederholen Sie dasselbe
- Suchen Sie weiter nach der Ulam-Nummer, bis wir unseren n-ten Begriff erhalten
Unten ist die Umsetzung der obigen Idee:
C++
// CPP code to print nth
// Ulam number
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
// Array to store Ulam Number
vector<int> arr;
// function to compute ulam Number
void ulam()
{
// push First 2 two term of the sequence
// in the array
// for further calculation
arr.push_back(1);
arr.push_back(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++) {
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.size() - 1; j++) {
for (int k = j + 1; k < arr.size(); k++) {
if (arr[j] + arr[k] == i) {
count++;
}
if (count > 1)
break;
}
if (count > 1)
break;
}
// If count is 1 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 1) {
// i is ulam number
arr.push_back(i);
}
}
}
// Driver code
int main()
{
// Pre compute Ulam Number sequence
ulam();
int n = 9;
// Print nth Ulam number
cout << arr[n - 1];
return 0;
}
Java
// JAVA code to print nth
// Ulam number
import java.util.*;
class GFG {
static final int MAX = 1000;
// Array to store Ulam Number
static Vector<Integer> arr = new Vector<Integer>();
// Function to compute ulam Number
static void ulam()
{
// push First 2 two term of the sequence
// in the array
// for further calculation
arr.add(1);
arr.add(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++) {
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.size() - 1; j++) {
for (int k = j + 1; k < arr.size(); k++) {
if (arr.get(j) + arr.get(k) == i) {
count++;
}
if (count > 1)
break;
}
if (count > 1)
break;
}
// If count is 2 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 1) {
// i is ulam number
arr.add(i);
}
}
}
// Driver code
public static void main(String[] args)
{
// pre compute Ulam Number sequence
ulam();
int n = 9;
// print nth Ulam number
System.out.println(arr.get(n - 1));
}
}
Python3
# Python3 code to print nth # Ulam number MAX = 1000 # Array to store Ulam Number arr = [] # function to compute ulam Number def ulam(): # push First 2 two term of the sequence # in the array # for further calculation arr.append(1); arr.append(2); # loop to generate Ulam number for i in range(3, MAX): count = 0; # traverse the array and check if # i can be represented as sum of # two distinct element of the array for j in range(len(arr) - 1): for k in range(j + 1, len(arr)): if (arr[j] + arr[k] == i): count += 1 if (count > 1): break; if (count > 1): break; # If count is 1 that means # i can be represented as sum of # two distinct terms of the sequence if (count == 1): # i is ulam number arr.append(i); # Driver code if __name__=='__main__': # Pre compute Ulam Number sequence ulam(); n = 9; # Print nth Ulam number print(arr[n - 1]) # This code is contributed by rutvik_56.
C#
// C# code to print nth
// Ulam number
using System;
using System.Collections.Generic;
class GFG
{
static readonly int MAX = 1000;
// Array to store Ulam Number
static List<int> arr = new List<int>();
// Function to compute ulam Number
static void ulam()
{
// push First 2 two term of
// the sequence in the array
// for further calculation
arr.Add(1);
arr.Add(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++)
{
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.Count - 1; j++)
{
for (int k = j + 1; k < arr.Count; k++)
{
if (arr[j] + arr[k] == i)
{
count++;
}
if (count > 1)
break;
}
if (count > 1)
break;
}
// If count is 2 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 1)
{
// i is ulam number
arr.Add(i);
}
}
}
// Driver code
public static void Main(String[] args)
{
// pre compute Ulam Number sequence
ulam();
int n = 9;
// print nth Ulam number
Console.WriteLine(arr[n - 1]);
}
}
// This code is contributed by Rajput-JI
Javascript
<script>
// Javascript code to print nth
// Ulam number
var MAX = 10000;
// Array to store Ulam Number
var arr = [];
// function to compute ulam Number
function ulam()
{
// push First 2 two term of the sequence
// in the array
// for further calculation
arr.push(1);
arr.push(2);
// loop to generate Ulam number
for (var i = 3; i < MAX; i++) {
var count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (var j = 0; j < arr.length - 1; j++) {
for (var k = j + 1; k < arr.length; k++) {
if (arr[j] + arr[k] == i) {
count++;
}
if (count > 1)
break;
}
if (count > 1)
break;
}
// If count is 1 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 1)
{
// i is ulam number
arr.push(i);
}
}
}
// Driver code
// Pre compute Ulam Number sequence
ulam();
var n = 9;
// Print nth Ulam number
document.write( arr[n - 1]);
// This code is contributed by noob2000.
</script>
Ausgabe:
16
Eine effiziente Lösung besteht darin, eine Hash-Tabelle zu verwenden, um die frühere Nummer der Sequenz zu speichern, sodass wir dies tun können, anstatt zwei Schleifen zu verwenden, um zu prüfen, ob „i“ als Summe zweier unterschiedlicher Terme auf genau eine Weise ausgedrückt werden kann oder nicht es in einer einzigen Schleife. Die Suche wird schnell sein, wenn wir eine Hash-Tabelle verwenden.
Unten ist die Umsetzung der obigen Idee:
C++
// Cpp code to print nth
// Ulam number
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
// Array to store Ulam Number
vector<int> arr;
// function to compute ulam Number
void ulam()
{
// Set to search specific Ulam number efficiently
unordered_set<int> s;
// push First 2 two term of the sequence
// in the array and set
// for further calculation
arr.push_back(1);
s.insert(1);
arr.push_back(2);
s.insert(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++) {
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.size(); j++) {
// Check if i-arr[j] exist in the array or not using set
// If yes, Then i can be represented as
// sum of arr[j] + (i- arr[j])
if (s.find(i - arr[j]) != s.end() && arr[j] != (i - arr[j]))
count++;
// if Count is greater than 2
// break the loop
if (count > 2)
break;
}
// If count is 2 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 2) {
// i is ulam number
arr.push_back(i);
s.insert(i);
}
}
}
// Driver code
int main()
{
// pre compute Ulam Number sequence
ulam();
int n = 9;
// print nth Ulam number
cout << arr[n - 1];
return 0;
}
Java
// JAVA code to print nth
// Ulam number
import java.util.*;
class GFG {
static final int MAX = 10000;
// Array to store Ulam Number
static Vector<Integer> arr = new Vector<Integer>();
// function to compute ulam Number
static void ulam()
{
// Set to search specific Ulam number efficiently
Set<Integer> s = new HashSet<Integer>();
// push First 2 two term of the sequence
// in the array and set
// for further calculation
arr.add(1);
s.add(1);
arr.add(2);
s.add(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++) {
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.size(); j++) {
// Check if i-arr[j] exist in the array or not using set
// If yes, Then i can be represented as
// sum of arr[j] + (i- arr[j])
if (s.contains(i - arr.get(j)) && arr.get(j) != (i - arr.get(j)))
count++;
// if Count is greater than 2
// break the loop
if (count > 2)
break;
}
// If count is 2 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 2) {
// i is ulam number
arr.add(i);
s.add(i);
}
}
}
// Driver code
public static void main(String[] args)
{
// pre compute Ulam Number sequence
ulam();
int n = 9;
// print nth Ulam number
System.out.println(arr.get(n - 1));
}
}
Python3
# Python3 code to print nth Ulam number MAX = 10000 # Array to store Ulam Number arr = [] # function to compute ulam Number def ulam(): # Set to search specific Ulam # number efficiently s = set() # push First 2 two term of the # sequence in the array and set # for further calculation arr.append(1) s.add(1) arr.append(2) s.add(2) # loop to generate Ulam number for i in range(3, MAX): count = 0 # traverse the array and check if # i can be represented as sum of # two distinct element of the array for j in range(0, len(arr)): # Check if i-arr[j] exist in the array # or not using set. If yes, Then i can # be represented as sum of arr[j] + (i- arr[j]) if (i - arr[j]) in s and arr[j] != (i - arr[j]): count += 1 # if Count is greater than 2 # break the loop if count > 2: break # If count is 2 that means # i can be represented as sum of # two distinct terms of the sequence if count == 2: # i is ulam number arr.append(i) s.add(i) # Driver Code if __name__ == "__main__": # pre compute Ulam Number sequence ulam() n = 9 # print nth Ulam number print(arr[n - 1]) # This code is contributed by Rituraj Jain
C#
// C# code to print nth
// Ulam number
using System;
using System.Collections.Generic;
class GFG
{
static readonly int MAX = 10000;
// Array to store Ulam Number
static List<int> arr = new List<int>();
// function to compute ulam Number
static void ulam()
{
// Set to search specific Ulam number efficiently
HashSet<int> s = new HashSet<int>();
// push First 2 two term of the sequence
// in the array and set
// for further calculation
arr.Add(1);
s.Add(1);
arr.Add(2);
s.Add(2);
// loop to generate Ulam number
for (int i = 3; i < MAX; i++)
{
int count = 0;
// traverse the array and check if
// i can be represented as sum of
// two distinct element of the array
for (int j = 0; j < arr.Count; j++)
{
// Check if i-arr[j] exist in the array
// or not using set If yes,
// Then i can be represented as
// sum of arr[j] + (i- arr[j])
if (s.Contains(i - arr[j]) &&
arr[j] != (i - arr[j]))
count++;
// if Count is greater than 2
// break the loop
if (count > 2)
break;
}
// If count is 2 that means
// i can be represented as sum of
// two distinct terms of the sequence
if (count == 2)
{
// i is ulam number
arr.Add(i);
s.Add(i);
}
}
}
// Driver code
public static void Main(String[] args)
{
// pre compute Ulam Number sequence
ulam();
int n = 9;
// print nth Ulam number
Console.WriteLine(arr[n - 1]);
}
}
// This code is contributed by Rajput-Ji
Ausgabe:
16
Falls Sie an Live-Kursen mit Experten teilnehmen möchten , beziehen Sie sich bitte auf DSA Live-Kurse für Berufstätige und Competitive Programming Live for Students .