要快速找到 A, B, C 使得 A×B×Cx4/13 最接近 D

目录

1.最慢的办法，最精确的，

2. 比较快，但精确较差的办法。

3.改进精确度后

4.性能和准确度测试

5.针对应用场景进一步优化速度

0. 取值范围

A取值范围 为(64, 128, 256,1024),

B为（1-255），

C为（1-256）

D的取值范围是0-20568221

1.最慢的办法，最精确的，

三层循环循环，每次要计算261120 ，比较慢， 如下：

void find_best_abc_slow(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;



    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
         
            for(uint32_t C=1; C<=256;C++)
            {
                // 计算当前值和误差
                uint32_t current_value = A * B * C *4/13;
                uint32_t error = (current_value > D) ? (current_value - D) : (D - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = C;
                }
            }
        }
    }
}

2. 比较快，但精确较差的办法。

代码实现如下：

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

// 动态计算最优解
void find_best_abc(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;

            // 剪枝：如果 A * B > D_prime，停止当前循环
            if (product_AB > D_prime) break;

            // 动态计算 C
            uint32_t C = D_prime / product_AB; // 整数除法计算 C

            // 检查 C 是否在合法范围
            if (C < 1 || C > 256) continue;

            // 计算当前值和误差
            uint32_t current_value = A * B * C;
            uint32_t error = (current_value > D_prime) ? (current_value - D_prime) : (D_prime - current_value);

            // 更新最优解
            if (error < *min_error) {
                *min_error = error;
                *best_A = A;
                *best_B = B;
                *best_C = C;
            }
        }
    }
}

3.改进精确度后

由于整法除法引起的精度问题，增加对于结果+-1的比较。

void find_best_abc_better(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;

            // 剪枝：如果 A * B > D_prime，停止当前循环
            if (product_AB > D_prime) break;

            // 动态计算 C
            uint32_t C = D_prime / product_AB; // 初步估算的 C 值

            // 检查 C 和其附近值（C-1, C, C+1）
            for (int offset = -1; offset <= 1; offset++) {
                uint32_t adjusted_C = C + offset;

                // 检查 C 是否在合法范围
                if (adjusted_C < 1 || adjusted_C > 256) continue;

                // 计算当前值和误差
                uint64_t current_value = (uint64_t)A * B * adjusted_C;
                uint32_t error = (current_value > D_prime) ? (current_value - D_prime) : (D_prime - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = adjusted_C;
                }
            }
        }
    }
}

4.性能和准确度测试

使用以下代码

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <time.h>

// 动态计算最优解
void find_best_abc(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;

            // 剪枝：如果 A * B > D_prime，停止当前循环
            if (product_AB > D_prime) break;

            // 动态计算 C
            uint32_t C = D_prime / product_AB; // 整数除法计算 C

            // 检查 C 是否在合法范围
            if (C < 1 || C > 256) continue;

            // 计算当前值和误差
            uint32_t current_value = A * B * C;
            uint32_t error = (current_value > D_prime) ? (current_value - D_prime) : (D_prime - current_value);

            // 更新最优解
            if (error < *min_error) {
                *min_error = error;
                *best_A = A;
                *best_B = B;
                *best_C = C;
            }
        }
    }

    uint32_t fix  = (  *best_A) * (*best_B) *  ( *best_C ) * 4 /13;
      *min_error   = (fix > D) ? (fix - D) : (D - fix);

}


void find_best_abc_better(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;

            // 剪枝：如果 A * B > D_prime，停止当前循环
            if (product_AB > D_prime) break;

            // 动态计算 C
            uint32_t C = D_prime / product_AB; // 初步估算的 C 值

            // 检查 C 和其附近值（C-1, C, C+1）
            for (int offset = -1; offset <= 1; offset++) {
                uint32_t adjusted_C = C + offset;

                // 检查 C 是否在合法范围
                if (adjusted_C < 1 || adjusted_C > 256) continue;

                // 计算当前值和误差
                uint64_t current_value = (uint64_t)A * B * adjusted_C;
                uint32_t error = (current_value > D_prime) ? (current_value - D_prime) : (D_prime - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = adjusted_C;
                }
            }
        }
    }

    uint32_t fix  = (  *best_A) * (*best_B) *  ( *best_C ) * 4 /13;
    *min_error   = (fix > D) ? (fix - D) : (D - fix);
}



void find_best_abc_slow(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;



    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
         
            for(uint32_t C=1; C<=256;C++)
            {
                // 计算当前值和误差
                uint32_t current_value = A * B * C *4/13;
                uint32_t error = (current_value > D) ? (current_value - D) : (D - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = C;
                }
            }
        }
    }
}


void find_best_abc_slow_better(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;
            if (product_AB > D_prime) break; // 剪枝: 如果 A * B 已经大于 D'，跳过后续 B 值

            // 枚举 C 的取值
            for (uint32_t C = 1; C <= 256; C++) {
                uint32_t current_value = A * B * C * 4 / 13;
                uint32_t error = (current_value > D) ? (current_value - D) : (D - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = C;
                }
            }
        }
    }
}




int main() {
    
    uint32_t best_A, best_B, best_C, min_error;

    clock_t start_time = clock();

    for(uint32_t D =1000;D<100000;D+=100)
    {
        // 计算最优解
        find_best_abc(D, &best_A, &best_B, &best_C, &min_error);

    }

    double elapsed_time = (double)(clock() - start_time) / CLOCKS_PER_SEC;
    printf("fast 运行时间: %.6f 秒\n", elapsed_time);


    start_time = clock();
    for(uint32_t D =1000;D<100000;D+=100)
    {
        // 计算最优解
        find_best_abc_better(D, &best_A, &best_B, &best_C, &min_error);

    }
    elapsed_time = (double)(clock() - start_time) / CLOCKS_PER_SEC;
    printf("better 运行时间: %.6f 秒\n", elapsed_time);


    
    start_time = clock();
    for(uint32_t D =1000;D<100000;D+=100)
    {
        // 计算最优解
        find_best_abc_slow(D, &best_A, &best_B, &best_C, &min_error);

    }
    elapsed_time = (double)(clock() - start_time) / CLOCKS_PER_SEC;
    printf("slow 运行时间: %.6f 秒\n", elapsed_time);



    for(uint32_t D =1000;D<100000;D+=100)
    {
        // 计算最优解
        find_best_abc(D, &best_A, &best_B, &best_C, &min_error);
        printf("FAST   D=%d 最优解: A = %d, B = %d, C = %d, 误差 = %d\n", D, best_A, best_B, best_C, min_error);

        find_best_abc_better(D, &best_A, &best_B, &best_C, &min_error);
        printf("BETTER D=%d 最优解: A = %d, B = %d, C = %d, 误差 = %d\n",D, best_A, best_B, best_C, min_error);

        find_best_abc_slow(D, &best_A, &best_B, &best_C, &min_error);
        printf("SLOW   D=%d最优解: A = %d, B = %d, C = %d, 误差 = %d\n",D, best_A, best_B, best_C, min_error);


    }

    return 0;
}

测试结果如下：

最快的算法比最慢的快 198倍

(base) $ gcc  findbest.c -o best
(base) $ ./best 
fast 运行时间: 0.004464 秒
better 运行时间: 0.011828 秒
slow 运行时间: 0.886645 秒
FAST   D=1000 最优解: A = 64, B = 1, C = 50, 误差 = 16
BETTER D=1000 最优解: A = 64, B = 1, C = 51, 误差 = 4
SLOW   D=1000最优解: A = 64, B = 1, C = 51, 误差 = 4
FAST   D=1100 最优解: A = 64, B = 1, C = 55, 误差 = 17
BETTER D=1100 最优解: A = 64, B = 1, C = 56, 误差 = 2
...
FAST   D=99900 最优解: A = 64, B = 57, C = 89, 误差 = 1
BETTER D=99900 最优解: A = 64, B = 57, C = 89, 误差 = 1
SLOW   D=99900最优解: A = 64, B = 57, C = 89, 误差 = 1

5.针对应用场景进一步优化速度

因为对于一个数值会多次取值，为了进一步改进速度，增加了一个cache层，把计算结果cache起，在下次使用时，快速查到cache中有没有，有的时候立即返回，无需计算。 cache的总数量为10个。

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

#define CACHE_SIZE 10 // 缓存的最大数量

// 定义缓存项结构
typedef struct {
    uint32_t D;          // 输入值
    uint32_t best_A;     // 最优解 A
    uint32_t best_B;     // 最优解 B
    uint32_t best_C;     // 最优解 C
    uint32_t min_error;  // 最小误差
} CacheEntry;

// 定义缓存
CacheEntry cache[CACHE_SIZE];
int cache_count = 0;

// 在缓存中查找目标值 D 的结果
int find_in_cache(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    for (int i = 0; i < cache_count; i++) {
        if (cache[i].D == D) {
            *best_A = cache[i].best_A;
            *best_B = cache[i].best_B;
            *best_C = cache[i].best_C;
            *min_error = cache[i].min_error;
            return 1; // 找到缓存
        }
    }
    return 0; // 未找到缓存
}

// 将计算结果存储到缓存中
void add_to_cache(uint32_t D, uint32_t best_A, uint32_t best_B, uint32_t best_C, uint32_t min_error) {
    if (cache_count < CACHE_SIZE) {
        // 如果缓存未满，直接添加
        cache[cache_count++] = (CacheEntry){D, best_A, best_B, best_C, min_error};
    } else {
        // 如果缓存已满，采用简单的替换策略（FIFO）
        for (int i = 1; i < CACHE_SIZE; i++) {
            cache[i - 1] = cache[i];
        }
        cache[CACHE_SIZE - 1] = (CacheEntry){D, best_A, best_B, best_C, min_error};
    }
}

// 动态计算最优解
void find_best_abc(uint32_t D, uint32_t *best_A, uint32_t *best_B, uint32_t *best_C, uint32_t *min_error) {
    // 首先查找缓存
    if (find_in_cache(D, best_A, best_B, best_C, min_error)) {
        return; // 如果找到缓存，直接返回
    }

    uint32_t A_values[] = {64, 128, 256, 1024}; // A 的可能取值
    *min_error = UINT32_MAX; // 初始化最小误差为最大值
    *best_A = 0;
    *best_B = 0;
    *best_C = 0;

    // 计算目标值 D'
    uint32_t D_prime = (uint32_t)((uint64_t)D * 13 / 4);

    // 枚举 A 的取值
    for (int i = 0; i < 4; i++) {
        uint32_t A = A_values[i];

        // 枚举 B 的取值
        for (uint32_t B = 1; B <= 255; B++) {
            uint32_t product_AB = A * B;

            // 剪枝：如果 A * B > D_prime，停止当前循环
            if (product_AB > D_prime) break;

            // 动态计算 C
            uint32_t C = D_prime / product_AB; // 初步估算的 C 值

            // 检查 C 和其附近值（C-1, C, C+1）
            for (int offset = -1; offset <= 1; offset++) {
                uint32_t adjusted_C = C + offset;

                // 检查 C 是否在合法范围
                if (adjusted_C < 1 || adjusted_C > 256) continue;

                // 计算当前值和误差
                uint64_t current_value = (uint64_t)A * B * adjusted_C;
                uint32_t error = (current_value > D_prime) ? (current_value - D_prime) : (D_prime - current_value);

                // 更新最优解
                if (error < *min_error) {
                    *min_error = error;
                    *best_A = A;
                    *best_B = B;
                    *best_C = adjusted_C;
                }
            }
        }
    }

    // 将计算结果存储到缓存中
    add_to_cache(D, *best_A, *best_B, *best_C, *min_error);
}

int main() {
    uint32_t D; // 目标值
    printf("请输入目标值 D (0 ~ 66846720): ");
    scanf("%u", &D);

    if (D > 66846720) {
        printf("输入值 D 超出范围！\n");
        return 1;
    }

    uint32_t best_A, best_B, best_C, min_error;

    // 计算最优解
    find_best_abc(D, &best_A, &best_B, &best_C, &min_error);

    // 输出结果
    printf("最优解: A = %u, B = %u, C = %u, 误差 = %u\n", best_A, best_B, best_C, min_error);

    return 0;
}