srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

2019-06-01から1ヶ月間の記事一覧

ブレゼンハムアルゴリズム

与えられた始点と終点の間に連続した点を置き、近似的な直線を引くためのアルゴリズムである。y = ax + b を近似する場合、ある整数 x に対して、y の値を計算し、その値を四捨五入して整数値にした値を近似値とすればよい。 この操作を始点から終点までのす…

pthreadによるスレッド間でのカウンタの共有

まず以下のプログラムのように、変数xを複数のスレッドが共有し、それぞれのスレッドがCOUNT_NUM回、変数xをインクリメントする処理を行う。 あるスレッドが(*(int *)i) += 1を実行する間に、他のスレッドも同じ部分を実行すると、競合が起こり、最終的に変…