スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ充

AOJでJOIの過去問の2周目をやっています。(1周目は去年の予選前に各問6以外をやりました)
正直、printf()がcout<<になったり、答えの格納先がベクトルになったくらいしか変化が見られないのですが……まあ、なんかこういうのは順番に解いていかないと気が済まない性分なので、やれるだけやります。

で、こちらの問題でひとつ感動的な性質?があったので紹介します。
座標をX,Y共に正方向に進む場合、ある点(i, j)までの経路数は(i - 1, j)までの経路数と(i, j - 1)までの経路数の合計の漸化式になるというものです。
これには恐れいった。圧倒的解法っ‥!ざわ‥ざわ‥
この問題は数Aの基礎でやるので手で解く分には問題ありませんが、プログラムだとどう組めばいいのか迷いますが、こんな方法があったとは。。
こういうのどんどん覚えてじゃんじゃん解けるようになりたいなー。というかこういうのを考えつく発想力が欲しい。


PHPが完全に詰まってますwwww
なんとかPEARをインストールしたはいいものの、DBが動かないでもうだめぽ状態ww
しばらく放置!ですぞ(^し^)!


↓コメ返

続きを読む

スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

拙者納得いかんぜよ

今日は普段より早く起きて、さらにやる気が妙にあるという日だったので、朝からAOJをやってたわけですよ。
JOIの問題(Volume5)を上からやってたんですが、0501で引っかかりました。

変換するのは、文字Xの変換後の文字をtrans[X]に入れておくという、この間アルゴリズム本で知ったのでいいんですが、問題は答えを保持する方法で。。

見てもらえればわかりますが、答えの文字列は最大で10^8 - 1文字になります。使用できるメモリは32MBです。データセットは複数あります。







ギブアーップ!
利根川さん…! 利根川先生っ…!


えええ、どうすりゃいいのこれ。
データセットの答え(string)をvectorにプッシュプッシュじゃ解けるわけないじゃあないですか。
助けて偉い人。

↓コード

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

PKU1032

PKUの1032です。
問題の内容は、

整数N(5≦N≦1000)を、いくつかの異なる整数の和に分解する。
たとえば7なら、

7 = 1 + 2 + 4
7 = 3 + 4

といった具合にです。
そして、その整数の積が最大となる整数の組を求めるというもの。
上の例なら、

1 * 2 * 4 = 8
3 * 4 = 12

ですから、求める組は(3, 4)となります。

で、以下とりあえず解いてみたソースです。
なんというか、いわゆるSO・U・A・TA・RIなので、N=25くらいで応答しなくなりますww
(2, 1, 1, 1), (1, 2, 1, 1), (1, 1, 2, 1), (1, 1, 1, 2)を区別するという糞仕様なので計算量はO(n!)というアレな答えですw デュフフwwwサーセンwww
ソースをそのまま書くと長さ的にアレなので、追記からどうぞ。

続きを読む

テーマ : プログラミング
ジャンル : コンピュータ

因数定理の

因数定理

P(x) = (x - α)Q(x) + R でx = αのとき P(α) = R
よってP(α) = 0 のとき (x - α)はP(x)の因数

に関して、P(α) = 0となるような数を見つける練習問題に疲れ果てたので、プログラムにやらせることに。


#include<iostream>
using namespace std;

int pow(int x, int y)
{
int result = 1;
while(y--) result *= x;
return result;
}

int main()
{
int a[10];
int n;

cout << "何次式ですか(3~9):";
cin >> n;

register int i, j, k;
for(i = 0; i < n; i++)
{
cout << n - i << "次の項の係数を入力:";
cin >> a[i];
}
cout << "定数項を入力:";
cin >> a[i];

i = (a[i] < 0) ? a[i] : -a[i];
j = -i;
int tmp;
for( ; i <= j; i++)
{
tmp = 0;
for(k = 0; k < n; k++)
{
tmp += pow(i, n - k) * a[k];
}
tmp += a[k];
if(tmp == 0)
{
cout << "発見: P(" << i << ") = 0" << endl;
}
}

return 0;
}


係数と定数項を入力すると、P(α) = 0となるαを小さい順に出力します。これを並べるだけで因数分解できちゃう! ふしぎ!


けどαが整数以外とかいう訳の分からない問題には未対応です。P(2/3)とかどうやって見つけるのよさ。
この辺で数Ⅱが疲れてきて数Bに逃げました。新しいこと面白いよほぉぉぉぉ

テーマ : プログラミング
ジャンル : コンピュータ

コードをキレイに貼れるようにしました!

タイトルの通りです!
↓こんな感じに色分けされます。


#include<iostream>
#include<vector>
using namespace std;

class Node
{
public:
vector<int> edges_to; //接続先ノードの番号
vector<int> edges_cost; //接続先ノードへの距離
int edges_num; //接続先ノードの数
bool done; //最短コストが確定したか否か
int cost; //最短コスト
int before; //最短経路での前のノード
Node(int *e, int *ec, int n);
void show(); //ノード情報を表示
};

Node::Node(int *e, int *ec, int n)
{
register int i;

for(i = 0; i < n; i++)
{
edges_to.push_back(e[i]);
edges_cost.push_back(ec[i]);
}
edges_num = n;
done = false;
cost = 999;
before = -1;
}

void Node::show()
{
vector<int>::iterator p, q;
p = edges_to.begin();
q = edges_cost.begin();
while(p != edges_to.end())
{
cout << "接続先[" << *p << "] 距離[" << *q << "]" << endl;
p++;
q++;
}
}

int main()
{
vector node;
int n, m;
int a[100], b[100];
register int i, j;
cout << "ノードの数:";
cin >> n;
for(i = 0; i < n; i++)
{
cout << "接続先の数: ";
cin >> m;
for(j = 0; j < m; j++)
{
cout << "接続先[" << j << "] <番号> <距離>: ";
cin >> a[j] >> b[j];
}
node.push_back(Node(a, b, m));
}

for(i = 0; i < n; i++)
{
cout << "ノード[" << i << "]: " << endl;
node[i].show();
}

int s, e;
cout << "スタート番号: ";
cin >> s;
cout << "ゴール番号: ";
cin >> e;

int current = s;

//スタートのノードはコスト0で初期化
node[current].cost = 0;
node[current].done = true;

int c, next, f, min;
while(1)
{
for(i = 0; i < node[current].edges_num; i++) //接続先ノードへの最短経路なら更新する
{
c = node[current].cost + node[current].edges_cost[i];
if(c < node[node[current].edges_to[i]].cost)
{

node[node[current].edges_to[i]].cost = c;
node[node[current].edges_to[i]].before = current;
}
}
min = 999;
f = 0;
for(i = 0; i < n; i++)
{
if(node[i].cost < min && node[i].done == false) //次の着目ノードを見つける(最短コストが最小のもの)
{
current = i;
min = node[i].cost;
f = 1;
}
}
if(!f) break;
node[current].done = true;
cout << "ノード[" << current << "]のコスト(" << node[current].cost << ")が確定" << endl;
}

cout << "最短距離: " << node[e].cost << endl;
cout << "最短経路: " << endl;

i = e;
do
{
cout << i << " ← ";
i = node[i].before;
}while(i != -1);



return 0;
}




これでいちいちテキストでアップしなくてもコードが晒せる!
導入するにあたって、何故か「sh_main.js」というファイル名だとアップできない現象にかなり手間取りました。
最終的には「sh_mainhoge.js」にしたらできたのですが。なんだったんだろう。


なんか長い行が枠線突き破ってますがキニシナイ方向でww


あと、<とか>を全角に直さないとならないのが面倒。まあ変換するプログラム書こうw

テーマ : プログラミング
ジャンル : コンピュータ

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。