Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // CercaLeSomme
- //
- // Created by Ale on 12/04/15.
- // Copyright (c) 2015 ABeltramo. All rights reserved.
- //
- #include <iostream>
- #include <vector>
- #include <fstream>
- using namespace std;
- int valFinale; //Valore che voglio ottenere
- int NElementi; //Numero di cifre totali
- vector<int> Input; //Vettore che contiene i numeri che mi passa
- vector<bool> Soluzione; //Contiene le posizioni dove bisogna mettere il +
- /*
- * Presi due interi A e B restituisce AB
- */
- int concatenaInt(int a, int b){
- int base = 1;
- while(base <= b)
- base *= 10;
- return (base * a) +b;
- }
- /*
- * Funzione ricorsiva:
- * mi genera tutte le possibili combinazioni di + che posso ottenere
- * Per ogni combinazione mi controlla se la somma dei numeri con quella combo
- * mi da il valore che cerco
- * In quel caso stampo
- */
- void trovaSoluzione(int pos){
- if(pos >= NElementi - 1){ //Passo base
- //Sono arrivato in fondo ad una sequenza
- //Controllo se questa sequenza di + mi porta alla soluzione corretta
- int ris = 0; //Risultato intermedio
- int pre = Input[0]; //Numero precedente
- for(int i=0;i<NElementi-1;i++){ //NElementi-1 perchè ci sono N-1 + nella sequenza
- if(Soluzione[i]){ //Ho messo un + quindi sommo il precedente
- ris += pre;
- pre = Input[i+1];
- }
- else{ // Non ho messo un + quindi devo concatenare
- pre = concatenaInt(pre,Input[i+1]);
- }
- }
- if(ris + pre == valFinale){ //Se ottengo il valore che cerco lo stampo
- for(int i=0;i<NElementi-1;i++){
- if(Soluzione[i])
- cout << i+1 << " ";
- }
- cout << endl;
- }
- }
- else{ //Passo ricorsivo
- Soluzione[pos] = true;
- trovaSoluzione(pos+1); //Uso il +
- Soluzione[pos] = false;
- trovaSoluzione(pos+1); //Non uso il +
- }
- }
- /*
- * MAIN()
- */
- int main() {
- ifstream inFile("input.txt");
- inFile >> NElementi;
- for(int i=0;i<NElementi;i++){
- int ele;
- inFile >> ele;
- Input.push_back(ele);
- }
- inFile >> valFinale;
- inFile.close();
- /*
- * FINE LETTURA DAL FILE
- */
- Soluzione.resize(NElementi); //Lo rendo della dimensione appropriata
- trovaSoluzione(0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement