3

C++ で並べ替えられたベクトルを使用して、2-SUM アルゴリズムのバリアントを実装しようとしています。タスクは、10^6 の整数を含むファイルを読み込み、合計が t になる個別の整数 (x と y) の数を計算することです。ここで、t は区間 [-10000, 10000] にあります。いくつかのテスト ケースでコードをテストしましたが、動作しているように見えますが、プログラミングの課題に対する正しい答えが得られません。これは Coursera Algorithms: Design and Analysis コース用です。したがって、この課題に対する正式なクレジットは受け取りません。助けていただければ幸いです。私のコードは以下にあります。

/*
 * TwoSums.cpp
 * Created on: 2013-08-05
 * 
 * Description: Implemented a variant of the 2-SUM algorithm for sums between -10000 and 10000.
 * The task was to compute the number of target values t in the interval [-10000,10000]
 * (inclusive) such that there are distinct numbers x,y in the input file (./HashInt.txt)
 * that satisfy x+y=t. The input file was taken from the Algorithms: Design and Analysis course
 * taught by Tim Roughgarden on Coursera.
 * 
 */

#include <iostream>
#include <vector>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <set>

#define LOWER -10000
#define HIGHER 10000

using namespace std;

const char* inputfile = "./HashInt.txt";

/*
 * Precondition: The inputfile is a file that contains integers, both 
 *               positive and negative. Each line contains an integer.
 * 
 * Postcondition: Every number in the file will be stored in vector V. 
 */

int ReadFile(vector<long>& V) {
    std::string line;
    std::ifstream infile;
    infile.open(inputfile);

    if(infile.fail())
    {
        cout << "Problem opening file.";
        return -1;
    }

    while (getline(infile, line)) {
        istringstream iss(line);
        long a;
        iss >> a;
        V.push_back(a);
    }

    return 0;
}

/*
 * Precondition: V is a sorted vector of integers
 * 
 * Postcondition: The number of target values (t) in the interval
 * [-10000,10000] will be displayed in stdout such that there
 * are distinct numbers x,y in the input file that satisfy x+y=t.
 */

void TwoSum (const vector<long>& V) {
    vector<long>::iterator x;
    vector<long>::iterator y;
    unsigned long count = 0;

    for (int i = LOWER; i <= HIGHER; ++i) {
        x = V.begin();
        y = V.end()-1;

        while (x != y) {
            long sum = *x + *y;
            if (sum == i) {
                count++;
                break;
            }

            else if(sum < i) {
                x+=1;
            }

            else {
                y-=1;
            }
        }
    }
    cout << "Count is: " << count << endl;
}

int main () {

    // Read integers, store in vector
    vector<long>V;
    if (ReadFile(V) < 0) return -1;

    // Erase duplicate numbers and sort vector
    set<long> s;
    unsigned long size = V.size();
    for( unsigned long i = 0; i < size; ++i ) s.insert( V[i] );
    V.assign(s.begin(),s.end() );

    // Implement 2-SUM algorithm for numbers between -10000 and 10000
    TwoSum(V);

    return 0;
}
4

2 に答える 2

0

このプログラムは、't' の値として使用する入力をユーザーに求めません。したがって、特定の t になる xy ペアの数は必要ないと仮定しています。あなたのプログラムは、't' のすべての可能な値を調べ、その合計になる xy ペアがあるかどうかを調べてから、't' の次の値に進みます。

于 2013-08-06T11:22:01.480 に答える