DouKaku? 4501 梅紫蘇: C++ STL。出力だけでなく、イテレー...(自然数の分割（別表現）)

Comment detail

C++ STL。出力だけでなく、イテレータまわしてるとこも遅いかも。

Pen4 3.06GHz, WinXP SP2, VS2005 count:204226 time[s]:19.937

#include <time.h>
#include <iostream>
#include <vector>

int young_sub(int n, int d, std::vector<int>& stack)
{
    if (n <= 0)
    {
        for (std::vector<int>::iterator li = stack.begin(); li != stack.end(); li++)
        {
            int n = *li;
            while (n--) { std::cout << "□"; }
            std::cout << std::endl;
        }
        std::cout << std::endl;
        return 1;
    }

    int count = 0;
    for (int i = ((n < d) ? n: d); i > 0; i--)
    {
        stack.push_back(i);
        count += young_sub(n - i, i, stack);
        stack.pop_back();
    }
    return count;
}

int young(int n)
{
    if (n < 1)
        return 0;
    std::vector<int> stack;
    stack.reserve(n);
    return young_sub(n, n, stack);
}

int main(int argc, char* argv[])
{
    if (argc < 2)
        return -1;
    int v = atoi(argv[1]);

    clock_t s = clock();
    int count = young(v);
    clock_t e = clock();

    std::cout << "count:"   << count << std::endl;
    std::cout << "time[s]:" << ((double)(e-s)/CLOCKS_PER_SEC) << std::endl;
    return count;
}

メモリ効率無視して、スピードを重視で修正。 coutへのリダイレクト数で時間が大幅に短縮できるようだったので、１パターン毎に文字列組み立ててcoutに流し込むようにしました。計算ロジック部分では、分割単位が１になったら残り全て１なので、そこで再帰を止めています。

Pen4 3.06GHz, WinXP SP2, VS2005 count:204226 time[s]:1.718

#include <time.h>
#include <iostream>
#include <vector>

int young_sub(int n, int d, std::vector<int>& stack)
{
    if ((n <= 0) || (d == 1))
    {
        std::string s("");
        for (std::vector<int>::iterator li = stack.begin(); li != stack.end(); li++)
        {
            int v = *li;
            while (v--) { s.append("□"); }
            s.append("\n");
        }
        for (int j = n; j > 0; j--) { s.append("□\n"); }
        s.append("\n");

        std::cout << s.c_str();
        return 1;
    }

    int count = 0;
    for (int i = ((n < d) ? n : d); i > 0; i--)
    {
        stack.push_back(i);
        count += young_sub(n - i, i, stack);
        stack.pop_back();
    }
    return count;
}

int young(int n)
{
    if (n < 1)
        return 0;
    std::vector<int> stack;
    stack.reserve(n);
    return young_sub(n, n, stack);
}

int main(int argc, char* argv[])
{
    if (argc < 2)
        return -1;
    int v = atoi(argv[1]);

    clock_t s = clock();
    int count = young(v);
    clock_t e = clock();

    std::cout << "count:"   << count << std::endl;
    std::cout << "time[s]:" << ((double)(e-s)/CLOCKS_PER_SEC) << std::endl;
    return count;
}

DouKaku?

Comment detail

Index

Feed

Other

Link

Pathtraq