logo

TechCodeview

Tulosta kaikki n-numeroiset luvut parittomien ja parillisten numeroiden erolla 1

Annettu kokonaisluku n joka edustaa numeroiden määrää. Tehtävänä on tulostaa kaikki n-numeroisia lukuja siten, että parillisten ja parittomien paikkojen numeroiden summan välinen absoluuttinen ero on täsmälleen 1 .
Huom : Numeron ei pitäisi alkaa (etunollia ei sallita).

lajitteluun arraylist java

Esimerkkejä:  



Syöte : n = 2
Lähtö : 10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

Syöte : n = 3
Lähtö : 100 111 120 122 131 133 142 144 153 155 164 166 175 177 186
188 197 199 210 221 230 232 241 243 252 254 263 265 274 276 285
287 296 298 320 331 340 342 351 353 362 364 373 375 384 386 395
397 430 441 450 452 461 463 472 474 483 485 494 496 540 551 560
562 571 573 582 584 593 595 650 661 670 672 681 683 692 694 760
771 780 782 791 793 870 881 890 892 980 991  

[Odotettu lähestymistapa] Rekursion käyttö

Ideana on rekursiivisesti generoi kaikki n-numeroiset luvut samalla summan seuraaminen numeroista klo jopa ja outoa kahdella muuttujalla. Tietyn paikan kohdalla täytämme sen kaikilla numeroilla 0-9 ja sen perusteella, onko nykyinen sijainti parillinen vai pariton, lisäämme parillista tai paritonta summaa. Käsittelemme nollan alussa olevat tapaukset erikseen, koska niitä ei lasketa numeroiksi.
Olemme noudattaneet nollapohjaista numerointia, kuten taulukkoindeksiä. eli johtavan (vasemman puolen) numeron katsotaan olevan parillisessa paikassa ja sen vieressä olevan numeron katsotaan olevan parittomassa paikassa ja niin edelleen.

C++ 
// C++ program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 #include    using namespace std; // Recursive function to generate numbers void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  vector<int> &res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (abs(evenSum - oddSum) == 1) {  res.push_back(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  } } // Function to prepare and collect valid numbers vector<int> findNDigitNums(int n) {    vector<int> res;  findNDigitNumsUtil(0 n 0 0 0 res);    return res; } // Driver code int main() {  int n = 2;  vector<int> res = findNDigitNums(n);  for (int i = 0; i < res.size(); i++) {  cout << res[i] << ' ';  }  return 0; }
Java 
// Java program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 import java.util.*; class GfG {  // Recursive function to generate numbers  static void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  ArrayList<Integer> res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (Math.abs(evenSum - oddSum) == 1) {  res.add(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  }  }  // Function to prepare and collect valid numbers  static ArrayList<Integer> findNDigitNums(int n) {  ArrayList<Integer> res = new ArrayList<>();  findNDigitNumsUtil(0 n 0 0 0 res);  return res;  }  // Driver code  public static void main(String[] args) {  int n = 2;  ArrayList<Integer> res = findNDigitNums(n);  // Print all collected valid numbers  for (int i = 0; i < res.size(); i++) {  System.out.print(res.get(i) + ' ');  }  } }
Python 
# Python program to print all n-digit numbers such that # the absolute difference between the sum of digits at # even and odd positions is 1 # Recursive function to generate numbers def findNDigitNumsUtil(pos n num evenSum oddSum res): # If number is formed if pos == n: # Check absolute difference condition if abs(evenSum - oddSum) == 1: res.append(num) return # Digits to consider at current position for d in range(10): # Skip leading 0 if pos == 0 and d == 0: continue # If position is even (0-based) add to evenSum if pos % 2 == 0: findNDigitNumsUtil(pos + 1 n num * 10 + d evenSum + d oddSum res) # If position is odd add to oddSum else: findNDigitNumsUtil(pos + 1 n num * 10 + d evenSum oddSum + d res) # Function to prepare and collect valid numbers def findNDigitNums(n): res = [] findNDigitNumsUtil(0 n 0 0 0 res) return res # Driver code if __name__ == '__main__': n = 2 res = findNDigitNums(n) # Print all collected valid numbers for i in range(len(res)): print(res[i] end=' ')
C# 
// C# program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 using System; using System.Collections.Generic; class GfG {  // Recursive function to generate numbers  static void findNDigitNumsUtil(int pos int n int num  int evenSum int oddSum  List<int> res) {  // If number is formed  if (pos == n) {  // Check absolute difference condition  if (Math.Abs(evenSum - oddSum) == 1) {  res.Add(num);  }  return;  }  // Digits to consider at current position  for (int d = 0; d <= 9; d++) {  // Skip leading 0  if (pos == 0 && d == 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 == 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  }  }  // Function to prepare and collect valid numbers  static List<int> findNDigitNums(int n) {  List<int> res = new List<int>();  findNDigitNumsUtil(0 n 0 0 0 res);  return res;  }  // Driver code  public static void Main(string[] args) {  int n = 2;  List<int> res = findNDigitNums(n);  // Print all collected valid numbers  for (int i = 0; i < res.Count; i++) {  Console.Write(res[i] + ' ');  }  } }
JavaScript 
// JavaScript program to print all n-digit numbers such that // the absolute difference between the sum of digits at // even and odd positions is 1 // Recursive function to generate numbers function findNDigitNumsUtil(pos n num evenSum oddSum res) {  // If number is formed  if (pos === n) {  // Check absolute difference condition  if (Math.abs(evenSum - oddSum) === 1) {  res.push(num);  }  return;  }  // Digits to consider at current position  for (let d = 0; d <= 9; d++) {  // Skip leading 0  if (pos === 0 && d === 0) {  continue;  }  // If position is even (0-based) add to evenSum  if (pos % 2 === 0) {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum + d oddSum res);  }  // If position is odd add to oddSum  else {  findNDigitNumsUtil(pos + 1 n num * 10 + d  evenSum oddSum + d res);  }  } } // Function to prepare and collect valid numbers function findNDigitNums(n) {  let res = [];  findNDigitNumsUtil(0 n 0 0 0 res);  return res; } // Driver code let n = 2; let res = findNDigitNums(n); // Print all collected valid numbers for (let i = 0; i < res.length; i++) {  process.stdout.write(res[i] + ' '); }

Lähtö 
10 12 21 23 32 34 43 45 54 56 65 67 76 78 87 89 98

Aika monimutkaisuus: O(9 × 10^(n-1)), koska jokaisessa numerossa on enintään 10 vaihtoehtoa (paitsi ensimmäisessä, jossa on 9).
Tilan monimutkaisuus: O(n + k) missä n on rekursion syvyys ja k on kelvollisten tulosten lukumäärä.