Advertisement
Guest User

Untitled

a guest
May 23rd, 2015
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. //
  2. // main.cpp
  3. // CercaLeSomme
  4. //
  5. // Created by Ale on 12/04/15.
  6. // Copyright (c) 2015 ABeltramo. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <fstream>
  12.  
  13. using namespace std;
  14.  
  15. int valFinale; //Valore che voglio ottenere
  16. int NElementi; //Numero di cifre totali
  17. vector<int> Input; //Vettore che contiene i numeri che mi passa
  18. vector<bool> Soluzione; //Contiene le posizioni dove bisogna mettere il +
  19.  
  20.  
  21. /*
  22. * Presi due interi A e B restituisce AB
  23. */
  24. int concatenaInt(int a, int b){
  25. int base = 1;
  26. while(base <= b)
  27. base *= 10;
  28. return (base * a) +b;
  29. }
  30.  
  31.  
  32. /*
  33. * Funzione ricorsiva:
  34. * mi genera tutte le possibili combinazioni di + che posso ottenere
  35. * Per ogni combinazione mi controlla se la somma dei numeri con quella combo
  36. * mi da il valore che cerco
  37. * In quel caso stampo
  38. */
  39. void trovaSoluzione(int pos){
  40. if(pos >= NElementi - 1){ //Passo base
  41. //Sono arrivato in fondo ad una sequenza
  42. //Controllo se questa sequenza di + mi porta alla soluzione corretta
  43. int ris = 0; //Risultato intermedio
  44. int pre = Input[0]; //Numero precedente
  45. for(int i=0;i<NElementi-1;i++){ //NElementi-1 perchè ci sono N-1 + nella sequenza
  46. if(Soluzione[i]){ //Ho messo un + quindi sommo il precedente
  47. ris += pre;
  48. pre = Input[i+1];
  49. }
  50. else{ // Non ho messo un + quindi devo concatenare
  51. pre = concatenaInt(pre,Input[i+1]);
  52. }
  53. }
  54. if(ris + pre == valFinale){ //Se ottengo il valore che cerco lo stampo
  55. for(int i=0;i<NElementi-1;i++){
  56. if(Soluzione[i])
  57. cout << i+1 << " ";
  58. }
  59. cout << endl;
  60. }
  61. }
  62. else{ //Passo ricorsivo
  63. Soluzione[pos] = true;
  64. trovaSoluzione(pos+1); //Uso il +
  65.  
  66. Soluzione[pos] = false;
  67. trovaSoluzione(pos+1); //Non uso il +
  68. }
  69. }
  70.  
  71.  
  72. /*
  73. * MAIN()
  74. */
  75. int main() {
  76. ifstream inFile("input.txt");
  77. inFile >> NElementi;
  78. for(int i=0;i<NElementi;i++){
  79. int ele;
  80. inFile >> ele;
  81. Input.push_back(ele);
  82. }
  83. inFile >> valFinale;
  84. inFile.close();
  85.  
  86. /*
  87. * FINE LETTURA DAL FILE
  88. */
  89.  
  90. Soluzione.resize(NElementi); //Lo rendo della dimensione appropriata
  91. trovaSoluzione(0);
  92.  
  93. return 0;
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement