[Lớp thuật toán hè 2015] Tài liệu và trao đổi buổi 8

[13520564]

Tính lũy thừa - sử dụng Bitwise & đệ quy

#include <stdio.h>

int power(int num, int n);

void main()
{
    printf("%d", power(3, 15));
}

int power(int num, int n)
{
    if (n == 1)
    {
        return num;
    }
    else
    {
        int result = 0;
        int i = 1;
        int t = 0;

        while ( i < n )        //find the maximum power of two
        {
            t = i;
            i = i << 1;
        }

        i = 1;
        result = num;

        while ( i < t )
        {
            result = result * result;
            i = i << 1;
        }                    //get num^t

        i = n - t;

        result = result * power(num, i);    //Calculate the remaing (n - t)

        return result;
    }
} 

[14520769]

Hàm luỹ thừa

int pow(int x, int n)
{
    if (!n)    
        return 1;
    else if (n == 1)
        return x;
    else if (n == 2)
        return x * x;
    else 
    {
        if (!(n % 2))
        {
            return pow(pow(x, n / 2), 2);
        }
        else
            return pow(pow(x, n / 2), 2) * x;
    }
} 

[13520376]

Max - Min

#include <stdio.h>

int max(int a[],int left, int right)
{
    int max1,max2;
    if (left==right) return a[left];
    else
    {
        max1=max(a,left,(left+right)/2);
        max2=max(a,(left+right)/2+1,right);
        if(max1>max2) return max1;
        else return max2;
    }
}

int min(int a[],int left, int right)
{
    int min1,min2;
    if (left==right) return a[left];
    else
    {
        min1=min(a,left,(left+right)/2);
        min2=min(a,(left+right)/2+1,right);
        if(min1<min2) return min1;
        else return min2;
    }
}

int main()
{
    int a[1000],n,i;
    printf("Nhap n: "); scanf("%d",&n);
    for (i=0;i<n;i++)
        scanf("%d",&a[i]);
    printf("\nMax: %d",max(a,0,n-1));
    printf("\nMin: %d",min(a,0,n-1));
    return 0;
} 

[14520052]

#include <stdio.h>
#include <stdlib.h>

int Max(int* A,int n)
{
    if (n==1)
        return A[0];
    else
    {
        int temp1, temp2;
        temp1 = Max (A,n/2);
        temp2 = Max (A+n/2,n-n/2);
        return temp1>temp2?temp1:temp2;
    }
}

main()
{
    int n,i;
    scanf("%d",&n);
    int A[n];
    for (i=0;i<n;i++)
    {
        A[i] = rand()%100;
        printf("%d ",A[i]);    
    }
    printf("\nMax: %d",Max (A,n));
} 

[13521005]

tìm max bằng đệ quy

int MAX(int *a, int n)
{
	if (n == 1)
		return *a;
	int d = n / 2;
	int m1 = MAX(a + d , d);
	int m2 = MAX(a, d);
	return max(m1, m2); // #define max(a , b) ((a > b) ? a : b)
}

[14520981]

Chia tiền bằng pp đệ quy & quay lui

code mình dùng pp đệ quy quay lui, sử dụng 1 vòng for

#include <stdio.h>
int x[50], t[50], n, h = 1;

void init()
{
    printf("\nNhap n = ");
    scanf("%d", &n);
    x[0] = 1;
    t[0] = 0;
}

void output(int k)
{
    printf("\n[%d]  %d = ", h, n);
    for (int i = 1; i < k; i++)
        printf(" %d + ", x[i]);
    printf("%d", x[k]);
    h++;
}

void Try(int i)
{
    for (int j = x[i - 1]; j <= ((n - t[i - 1]) / 2); j++)
    {
        x[i] = j;
        t[i] = t[i - 1] + j;
        Try(i + 1);
    }
    x[i] = n - t[i - 1];
    output(i);
}

int main()
{
    init();
    Try(1);
} 

[14520052]

#include <iostream>
using namespace std;
#define MAX 10

int n,m;
int A[MAX];            //mang luu loai tien
int result[MAX];    //mang luu ket qua

void print(int* number,int size);
void back(int money, int i);

main()
{
    cout<<"So tien: "; cin>>n;
    cout<<"So loai tien: "; cin>>m;
    for (int i=0; i<m; i++)
    {
        cout<<"A["<<i<<"] = ";
        cin>>A[i];
    }
    back(n,0);
}

void print(int* number,int size)
{
    int i;
    for (i=0;i<size-1;i++)
        printf("%2d x%2d +",A[i],number[i]);
    printf("%2d x%2d\n",A[i],number[i]);
}

void back(int money, int i)
{
    if (money==0)
        print(result, m);
    else if (i<m)
    {
        int temp = money/A[i];
        for (int k=0; k<=temp; k++)
        {
            result[i] = k;
            back(money - k*A[i], i+1);    
        }
    }
} 

[toannv]

Ngày mai phòng máy sẽ mở cửa lúc 9:30 và học lúc 10:00.
Các bạn sẽ tiếp tục làm về đệ qui.