ぶんかつせんりゃく

7632 ワード

メモを取る!
(一)集計ソート:

#include <stdio.h>
#include <stdlib.h>
#include <string>
typedef long long LL;
using namespace std;

/* T(n) = 2T(n/2) + ⊙(n) = nlog(n) */
void Merge_sort(int *A,int x,int y,int *t) /* x ，y  */
{  
    if(y - x > 1){  
        int m = x + (y - x) / 2;  
        int p = x,q = m,i = x;  
        Merge_sort(A, x, m, t);  
        Merge_sort(A, m, y, t);  
        while(p < m || q < y){  
            if(q >= y || (p < m && A[p] <= A[q]))
                t[i++] = A[p++];  
            else t[i++] = A[q++];  
        }  
        for(i=x; i<y; i++)
            A[i] = t[i];  
    }  
}  

int main()
{
	int t[15];
	int s[] = {4, 1, 7, 6, 3, 8, 2, 5, 0, 9};
	Merge_sort(s, 0, 10, t);
	int i;
	for(i=0; i<10; i++)
		printf("%d ", s[i]);
	printf("
");
	return 0;
}

(二)二分検索:
再帰でその中の分治思想を体得して、もちろんwhile循環で解決することができます!

#include <stdio.h>
#include <stdlib.h>
#include <string>
typedef long long LL;
using namespace std;

/* T(n) = T(n/2) + ⊙(1) = log(n) */

int Binary_find(int key, int left, int right, int *a)
{
	int mid = left + (right - left) / 2;
	if(a[mid] == key) return mid;
	else if(a[mid] > key) return Binary_find(key, left, mid - 1, a);
	else if(a[mid] < key) return Binary_find(key, mid + 1, right, a);
}

int main()
{
	int a[] = {1, 3, 4, 6, 7, 9, 12, 14, 23, 24};
	int i;
	int ans;
	for(i=0; i<8; i++){
		ans = Binary_find(a[i], 0, 7, a);
		printf("%d
", ans);
	}
	return 0;
}

(三)xのn次方:
ライブラリ関数の中のdouble pow(double x,double y)はもっと完璧で、指数は浮動小数点型であることができます.ここではdouble Pow(double x,int n)を手書きで書きます.

#include <stdio.h>
#include <stdlib.h>
#include <string>
typedef long long LL;
using namespace std;

/* T(n) = T(n/2) + ⊙(1) = log(n) */

double f(double x, int n)
{
	if(1 == n) return x;
	int mid = (n>>1);
	double s = f(x, mid);
	if(n & 1) return s * s * x;
	else return s * s;
}

double Pow(double x, int n)
{
	if(0 == x && n > 0) return 0.0;
	else if(0 == n) return 1.0;
	else if(n > 0) return f(x, n);
	else if(n < 0) return (1/f(x, -n));
}

int main()
{
	double x;
	int n;
	while(~scanf("%lf%d", &x, &n)){
		printf("%0.6lf
", Pow(x, n));
		printf("%0.6lf
", pow(x, n));
	}
}

(四)フィボナッチ(Fibonacci)数列:
再帰は最も愚かな方法であり、反復は⊙(n)の複雑さであり、行列の高速べき乗は⊙(log(n))の複雑さに達することができる.
F(n)はn番目のフィボナッチ数にこのような関係があることを示す.
行列F(N＋1)F(N)＝行列1のN次方程式
F(N) F(N-1) 1 0
数学的帰納法で証明できる.したがって,結果は通常の行列の高速べき乗である.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include <iostream>

using namespace std;

int cnt;

/*   */
LL Fibonacci(int n)
{
	cnt++;
	if(1 == n || 2 == n) return 1;
	else return Fibonacci(n - 1) + Fibonacci(n - 2);
}

/* T(n) = ⊙(n) */
LL Fibonacci1(int n)
{
	LL a[100000];
	a[1] = a[2] = 1;
	int i;
	for(i=3; i<=n; i++)
		a[i] = a[i - 1] + a[i - 2];
	return a[n];
}

typedef struct
{
    LL a[2][2];
}Matrix;

Matrix A, B;

Matrix Matrix_mul(Matrix X, Matrix Y)  
{  
    Matrix tmp;  
    memset(tmp.a, 0, sizeof(tmp));  
    int i,j,k;  
    for(i=0; i<2; i++)  
        for(j=0; j<2; j++)  
            for(k=0; k<2; k++)
                tmp.a[i][j] += X.a[i][k] * Y.a[k][j];  
    return tmp;  
}  

/* T(n) = ⊙(logn) */
LL Fibonacci2(int n)
{
	A.a[0][0] = 1;
	A.a[0][1] = 1;
	A.a[1][0] = 1;
	A.a[1][1] = 0;
	B.a[0][0] = 1;
	B.a[0][1] = 0;
	B.a[1][0] = 0;
	B.a[1][1] = 1;
	while(n)
	{
		if(n & 1) B = Matrix_mul(B, A);
		A = Matrix_mul(A, A);
		n >>= 1;
	}
	return B.a[0][0];
}

int main()
{
	int i;
	int text = 4;
	LL ans = Fibonacci1(text);
	//long begtime = clock();
	FILETIME beg,end;  
    GetSystemTimeAsFileTime(&beg);  
	for(i=0; i<100000; i++)
		Fibonacci2(text);
    GetSystemTimeAsFileTime(&end);
    long time = (end.dwLowDateTime-beg.dwLowDateTime);  
	//long endtime = clock();
    //cout<<endtime - begtime<<endl;  
	cout << time <<endl;
	cout << ans <<endl;
}

(五)ストラソン行列乗算:
ネット上のやり方を参考にして,この行列乗算を書き換え,4次行列検証を用いた.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
#include <iostream>
typedef long long LL;
using namespace std;

typedef int INT;
#define N 4 

typedef struct matrix
{
	INT a[N][N];
	matrix()
	{
		memset(a, 0, sizeof(a));
	}
}Matrix;

void Matrix_mul(const Matrix A, const Matrix B, Matrix &C)
{
	memset(C.a, 0, sizeof(C.a));
	int i,j,k;
	for(i=0; i<2; i++)
		for(j=0; j<2; j++)
			for(k=0; k<2; k++)
				C.a[i][j] += A.a[i][k] * B.a[k][j];
}

void Matrix_add(const int n, const Matrix A, const Matrix B, Matrix &C)
{
	memset(C.a, 0, sizeof(C.a));
	int i,j;
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			C.a[i][j] = A.a[i][j] + B.a[i][j];
}

void Matrix_sub(const int n, const Matrix A, const Matrix B, Matrix &C)
{
	memset(C.a, 0, sizeof(C.a));
	int i,j;
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			C.a[i][j] = A.a[i][j] - B.a[i][j];
}

void Strassen(INT n, const Matrix A, const Matrix B, Matrix &C)
{
	Matrix A11, A12, A21, A22;
	Matrix B11, B12, B21, B22;
	Matrix C11, C12, C21, C22;
	Matrix M1, M2, M3, M4, M5, M6, M7;
	Matrix At, Bt, Mt, Mt1;

	if(2 == n) Matrix_mul(A, B, C);
	else{
		n /= 2;
		int i, j;
		for(i=0; i<n; i++)
			for(j=0; j<n; j++){
				A11.a[i][j] = A.a[i][j];
				A12.a[i][j] = A.a[i][j + n];
				A21.a[i][j] = A.a[i + n][j];
				A22.a[i][j] = A.a[i + n][j + n];
				B11.a[i][j] = B.a[i][j];
				B12.a[i][j] = B.a[i][j + n];
				B21.a[i][j] = B.a[i + n][j];
				B22.a[i][j] = B.a[i + n][j + n];
			}

		Matrix_sub(n, A12, A22, At);
		Matrix_add(n, B21, B22, Bt);
		Strassen(n, At, Bt, M1);

		Matrix_add(n, A11, A22, At);
		Matrix_add(n, B11, B22, Bt);
		Strassen(n, At, Bt, M2);

		Matrix_sub(n, A11, A21, At);
		Matrix_add(n, B11, B12, Bt);
		Strassen(n, At, Bt, M3);

		Matrix_add(n, A11, A12, At);
		Strassen(n, At, B22, M4);

		Matrix_sub(n, B12, B22, Bt);
		Strassen(n, A11, Bt, M5);

		Matrix_sub(n, B21, B11, Bt);
		Strassen(n, A22, Bt, M6);

		Matrix_add(n, A21, A22, At);
		Strassen(n, At, B11, M7);

		/* sub_C */
		Matrix_add(n, M6, M1, Mt);
		Matrix_add(n, Mt, M2, Mt1);
		Matrix_sub(n, Mt1, M4, C11);

		Matrix_add(n, M5, M4, C12);

		Matrix_add(n, M6, M7, C21);

		Matrix_sub(n, M5, M3, Mt);
		Matrix_add(n, Mt, M2, Mt1);
		Matrix_sub(n, Mt1, M7, C22);

		for(i=0; i<n; i++)
			for(j=0; j<n; j++){
				C.a[i][j] = C11.a[i][j];
				C.a[i][j + n] = C12.a[i][j];
				C.a[i + n][j] = C21.a[i][j];
				C.a[i + n][j + n] = C22.a[i][j];
			}
	}
}

int main()
{
	Matrix A, B, C;
	A.a[0][0] = 1;
	A.a[0][1] = 0;
	A.a[0][2] = 2;
	A.a[0][3] = 1;
	A.a[1][0] = 0;
	A.a[1][1] = 3;
	A.a[1][2] = 1;
	A.a[1][3] = 2;
	A.a[2][0] = 0;
	A.a[2][1] = 0;
	A.a[2][2] = 2;
	A.a[2][3] = 2;
	A.a[3][0] = 2;
	A.a[3][1] = 3;
	A.a[3][2] = 0;
	A.a[3][3] = 1;

	B.a[0][0] = 2;
	B.a[0][1] = 1;
	B.a[0][2] = 0;
	B.a[0][3] = 0;
	B.a[1][0] = 0;
	B.a[1][1] = 1;
	B.a[1][2] = 1;
	B.a[1][3] = 1;
	B.a[2][0] = 1;
	B.a[2][1] = 0;
	B.a[2][2] = 2;
	B.a[2][3] = 2;
	B.a[3][0] = 3;
	B.a[3][1] = 0;
	B.a[3][2] = 2;
	B.a[3][3] = 1;

	Strassen(N, A, B, C);

	int i,j;
	for(i=0; i<N; i++){
		for(j=0; j<N; j++)
			printf("%-4d", C.a[i][j]);
		printf("
");
	}
	return 0;
}

Py&djangoノート

Vue.jsコンポーネントの再使用