羊城杯有一道题目本来逻辑已经很清晰了，但是因为看不懂算法，还是做不出来，没想到叫 DCT，什么狗屎玩意，根本没听过。气死了，只能学习一下，翻 DASCTF 的一道安卓逆向发现也涉及到 DCT，那说明这可能偶尔会出现在题目当中，那就学！

DCT 全称为 Discrete Cosine Transform，即离散余弦变换。DCT 变换属于傅里叶变换的一种，常用于对信号和图像（包括图片和视频）进行数据压缩的基础。

感觉它可能属于某种专业学习的内容，我们这里只学习一下它的公式和算法实现，不去深究它的应用。而且只是学习简单的一维离散余弦变换，因为这玩意有二维的。

参考文章

数字信号处理 — 一维离散余弦变换 (python 实战)-CSDN 博客

离散余弦变换

一维 DCT 的变换公式如下

x [n] 为输入的离散序列，n 的值为 0 到 N-1，N 是我们输入的个数

X [μ] 为离散余弦变换后的结果，是离散余弦变换的系数，μ 的值也为 0 到 N-1

我们假设 N 为 4，则可以将计算等式用矩阵表示。

我们暂且将中间的矩阵称为 A 矩阵，则 X[μ] = Ax[n]

这里的 E (μ) 是归一化系数，满足下图情况，它可以使得矩阵 A 保持正交。

我们输入为几个，就可以相对应获得几个 DCT 系数。一维离散余弦变换的 C 语言实现如下

#include <stdio.h>
#include <stdint.h>
#include <stdio.h>
#include <math.h>
 
#define N 8 //输入信号的长度
void dct(int input[], double output[]) {
	double alpha;
	double sum;
	int i, j;
	for (i = 0; i < N; i++) {
		if (i == 0) {
			alpha = sqrt(1.0 / N);
		}
		else {
			alpha = sqrt(2.0 / N);
		}
		sum = 0;
 
		for (j = 0; j < N; j++) {
			sum += input[j] * cos((2 * j + 1) * i * M_PI / (2 * N));
		}
		output[i] = alpha * sum;
	}
}
 
int main()
{
	int input[N] = { 1,2,3,4,5,6,7,8 }; //输入信号
	double output[N];  //变换后的信号
	int i;
 
	dct(input, output);
 
	printf("DCT结果：");
	for (i = 0; i < N; i++) {
		printf("%lf\n", output[i]);
	}
	printf("\n");
 
	return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

Python 的代码实现如下

import numpy as np
 
def dct1d(x):
    N = len(x)
    X = np.zeros(N)
 
    for k in range(N):
        sum_val = 0.0
        for n in range(N):
            sum_val += x[n] * np.cos((np.pi / N) * (n + 0.5) * k)
        alpha = np.sqrt(1.0 / N) if k == 0 else np.sqrt(2.0 / N)
        X[k] = alpha * sum_val
 
    return X
def main():
    # 示例数据
    x = []  # 输入的原始数据
 
    # 计算DCT
    X = dct1d(x)
 
    # 打印结果
    print("DCT结果:")
    print(X)
 
 
if __name__ == "__main__":
    main()

				

					
				
				

					
				
				

					
				
				

					
				
			

逆离散余弦变换

DCT 是可逆的，意味着我们可以通过逆 DCT（IDCT）从频域信号恢复原始信号，前提是没有对 DCT 系数进行过度的削减。

逆离散余弦变换（IDCT）是离散余弦变换（DCT）的逆过程，IDCT 的全称是 Inverse Discrete Cosine Transform。

直接贴一个解密 Python 脚本

import numpy as np
s1=[]
#待解密数据
N=
#待解密数据数组长度
A = np.array([[np.cos((j + 0.5) * i * np.pi /  N) for j in range( N)] for i in range( N)])
b = np.array([s1[i] / np.sqrt(1.0 /  N) if i == 0 else s1[i] / np.sqrt(2.0 /  N) for i in range( N)])
solution, residuals, rank, s = np.linalg.lstsq(A, b, rcond=None)
print("Result:")
print(solution)

				

					
				
				

					
				
				

					
				
				

					
				
			

这是 C 语言代码的是实现

#include <stdio.h>
#include <math.h>
 
#define N 8  // 变换长度
 
// 计算IDCT
void idct(float* input, float* output) {
    int u, x;
    float sum;
 
    // IDCT的余弦系数
    float Cx, Cu;
    float pi = 3.14159265358979323846;
 
    // IDCT公式计算
    for (x = 0; x < N; ++x) {
        sum = 0.0;
        for (u = 0; u < N; ++u) {
            if (u == 0) {
                Cu = sqrt(1.0 / N);
            }
            else {
                Cu = sqrt(2.0 / N);
            }
            Cx = cos((2 * x + 1) * u * pi / (2 * N));
            sum += Cu * input[u] * Cx;
        }
        output[x] = sum;
    }
}
int main() {
    float input[N] = { };  // 输入的DCT系数
    float output[N];       // 解密后的时域信号
 
    // 计算IDCT
    idct(input, output);
 
    // 打印结果
    printf("IDCT Result:\n");
    for (int i = 0; i < N; i++) {
        printf("%f ", output[i]);
    }
    printf("\n");
    return 0;
}

				

					
				
				

					
				
				

					
				
				

					
				
			

建议还是用 Python 代码，即简便，而且可能没有 C 语言那么容易出现问题。