fork(2) download
copy 
  1. from itertools import combinations
  2. import time
  3. import threading
  4. from collections import defaultdict
  5. import math
  6. from multiprocessing import Pool
  7.  
  8. # 配置参数（优化阈值）
  9. TARGET = 241327  # 目标值
  10. BASE_VALUES = [36.5, 41.5, 59,68.5, 74, 91.5]  # 基础系数列表
  11. FLUCTUATION = 1.0  # 系数波动范围
  12. MAX_SOLUTIONS = 3  # 每个组合的最大解数量
  13. SOLVER_TIMEOUT = 180  # 求解超时时间(秒)
  14. THREE_VAR_THRESHOLD = 259000  # 使用三个变量的阈值（调整为259000）
  15. PRODUCT_RANGE_THRESHOLD = 125000  # 乘积范围限制阈值（调整为125000）
  16. HIGH_TARGET_THRESHOLD = 259000  # 更高目标值阈值（调整为259000）
  17. SHOW_PROGRESS = True  # 是否显示进度
  18. MAX_SOLUTIONS_PER_COMB = 100  # 每个组合的最大解数量，用于提前终止
  19. USE_MULTIPROCESSING = True  # 是否使用多进程加速
  20.  
  21. def is_valid_product(p):
  22.     """检查单个乘积是否在有效范围内"""
  23.     if TARGET > PRODUCT_RANGE_THRESHOLD:  # TARGET > 125000
  24.         if TARGET > HIGH_TARGET_THRESHOLD:  # TARGET > 259000
  25.             return p <= 125000  # 单个乘积上限
  26.         else:  # 125000 < TARGET <= 259000
  27.             return 74000 <= p <= 125000  # 单个乘积范围
  28.     else:  # TARGET <= 125000
  29.         return True  # 小目标值取消所有限制
  30.  
  31. def find_single_variable_solutions(values):
  32.     """查找单个数的解（a*x = TARGET）"""
  33.     solutions = []
  34.     for a in values:
  35.         quotient = TARGET / a
  36.         if quotient != int(quotient):
  37.             continue
  38.         x = int(quotient)
  39.         if 1 <= x <= 10000 and is_valid_product(a * x):
  40.             solutions.append((a, x))
  41.             if len(solutions) >= MAX_SOLUTIONS:
  42.                 break
  43.     return solutions
  44.  
  45. def find_two_variable_solutions(values):
  46.     """优化的双变量求解算法"""
  47.     solutions = defaultdict(list)
  48.     for i, a in enumerate(values):
  49.         for b in values[i:]:
  50.             seen_xy = set()
  51.             max_x = math.floor((TARGET - b) / a)
  52.             min_x = max(1, math.ceil((TARGET - b * 10000) / a))
  53.  
  54.             if max_x < min_x:
  55.                 continue
  56.  
  57.             x_count = max_x - min_x + 1
  58.             x_step = max(1, x_count // 1000)
  59.  
  60.             for x in range(min_x, max_x + 1, x_step):
  61.                 remainder = TARGET - a * x
  62.  
  63.                 if remainder < b:
  64.                     break
  65.  
  66.                 if remainder > b * 10000:
  67.                     continue
  68.  
  69.                 if remainder % b == 0:
  70.                     y = remainder // b
  71.                     if 1 <= y <= 10000 and is_valid_product(b * y):
  72.                         xy_pair = (x, y) if a <= b else (y, x)
  73.                         if xy_pair not in seen_xy:
  74.                             seen_xy.add(xy_pair)
  75.                             solutions[(a, b)].append((a, x, b, y))
  76.                             if len(solutions[(a, b)]) >= MAX_SOLUTIONS_PER_COMB:
  77.                                 break
  78.     return solutions
  79.  
  80. def process_three_var_combination(args):
  81.     """处理三变量组合的辅助函数，用于并行计算"""
  82.     a, b, c, value_ranges, target = args
  83.     solutions = []
  84.     seen_xyz = set()
  85.  
  86.     min_x, max_x = value_ranges[a]
  87.     x_count = max_x - min_x + 1
  88.     x_step = max(1, x_count // 1000)
  89.  
  90.     for x in range(min_x, max_x + 1, x_step):
  91.         ax = a * x
  92.         if not is_valid_product(ax):
  93.             continue
  94.  
  95.         remainder1 = target - ax
  96.         if remainder1 < 0:
  97.             break
  98.  
  99.         max_y = math.floor((remainder1 - c) / b)
  100.         min_y = max(1, math.ceil((remainder1 - c * 10000) / b))
  101.  
  102.         if max_y < min_y:
  103.             continue
  104.  
  105.         y_count = max_y - min_y + 1
  106.         y_step = max(1, y_count // 100)
  107.  
  108.         for y in range(min_y, max_y + 1, y_step):
  109.             by = b * y
  110.             if not is_valid_product(by):
  111.                 continue
  112.  
  113.             remainder2 = remainder1 - by
  114.             if remainder2 < 0:
  115.                 break
  116.  
  117.             if remainder2 > c * 10000:
  118.                 continue
  119.  
  120.             if remainder2 % c == 0:
  121.                 z = remainder2 // c
  122.                 if 1 <= z <= 10000 and is_valid_product(c * z):
  123.                     xyz_tuple = tuple(sorted([x, y, z]))
  124.                     if xyz_tuple not in seen_xyz:
  125.                         seen_xyz.add(xyz_tuple)
  126.                         solutions.append((a, x, b, y, c, z))
  127.                         if len(solutions) >= MAX_SOLUTIONS_PER_COMB:
  128.                             return solutions
  129.  
  130.     return solutions
  131.  
  132. def find_three_variable_solutions(values):
  133.     """优化的三变量求解算法，使用并行计算"""
  134.     solutions = defaultdict(list)
  135.     sorted_values = sorted(values)
  136.  
  137.     # 预计算每个系数的有效范围
  138.     value_ranges = {}
  139.     for a in sorted_values:
  140.         min_x = max(1, math.ceil(74000 / a))
  141.         max_x = min(10000, math.floor(125000 / a))
  142.         value_ranges[a] = (min_x, max_x)
  143.  
  144.     combinations_list = []
  145.     for i, a in enumerate(sorted_values):
  146.         for j in range(i + 1, len(sorted_values)):
  147.             b = sorted_values[j]
  148.             for k in range(j + 1, len(sorted_values)):
  149.                 c = sorted_values[k]
  150.                 combinations_list.append((a, b, c, value_ranges, TARGET))
  151.  
  152.     if USE_MULTIPROCESSING:
  153.         with Pool() as pool:
  154.             results = pool.map(process_three_var_combination, combinations_list)
  155.  
  156.         for i, (a, b, c, _, _) in enumerate(combinations_list):
  157.             if results[i]:
  158.                 solutions[(a, b, c)] = results[i]
  159.     else:
  160.         total_combinations = len(combinations_list)
  161.         for i, (a, b, c, _, _) in enumerate(combinations_list):
  162.             res = process_three_var_combination((a, b, c, value_ranges, TARGET))
  163.             if res:
  164.                 solutions[(a, b, c)] = res
  165.  
  166.             if SHOW_PROGRESS and i % 10 == 0:
  167.                 print(f"\r三变量组合进度: {i}/{total_combinations} 组", end='')
  168.  
  169.     if SHOW_PROGRESS and not USE_MULTIPROCESSING:
  170.         print(f"\r三变量组合进度: {total_combinations}/{total_combinations} 组 - 完成")
  171.  
  172.     return solutions
  173.  
  174. def find_balanced_solutions(solutions, var_count, num=2):
  175.     """从所有解中筛选出最平衡的解"""
  176.     if var_count == 1 or not solutions:
  177.         return solutions
  178.  
  179.     balanced = []
  180.     for sol in solutions:
  181.         vars = sol[1::2]  # 获取解中的变量值
  182.         diff = max(vars) - min(vars)  # 计算变量之间的最大差值
  183.         balanced.append((diff, sol))
  184.  
  185.     # 按差值排序，返回差值最小的解
  186.     return [s for _, s in sorted(balanced, key=lambda x: x[0])[:num]]
  187.  
  188. def find_original_solutions(solutions, balanced_solutions, num=3):
  189.     """从剩余解中获取原始顺序的解"""
  190.     if not solutions:
  191.         return []
  192.  
  193.     remaining = [s for s in solutions if s not in balanced_solutions]
  194.     return remaining[:num]
  195.  
  196. def display_solutions(solutions_dict, var_count):
  197.     """优化的解显示函数"""
  198.     if not solutions_dict:
  199.         return
  200.  
  201.     print(f"\n找到 {len(solutions_dict)} 组{var_count}变量解：")
  202.  
  203.     for i, (coeffs, pair_solutions) in enumerate(sorted(solutions_dict.items()), 1):
  204.         balanced = find_balanced_solutions(pair_solutions, var_count)
  205.         original = find_original_solutions(pair_solutions, balanced)
  206.         all_display = balanced + original
  207.  
  208.         if var_count == 1:
  209.             a = coeffs
  210.             print(f"\n{i}. 组合: a={a} ({len(pair_solutions)} 个有效解)")
  211.         elif var_count == 2:
  212.             a, b = coeffs
  213.             print(f"\n{i}. 组合: a={a}, b={b} ({len(pair_solutions)} 个有效解)")
  214.         else:
  215.             a, b, c = coeffs
  216.             print(f"\n{i}. 组合: a={a}, b={b}, c={c} ({len(pair_solutions)} 个有效解)")
  217.  
  218.         for j, sol in enumerate(all_display, 1):
  219.             tag = "[平衡解]" if j <= len(balanced) else "[原始解]"
  220.  
  221.             if var_count == 1:
  222.                 a, x = sol
  223.                 print(f"  {j}. x={x}, a*x={a*x:.1f}, 总和={a*x:.1f} {tag}")
  224.             elif var_count == 2:
  225.                 a, x, b, y = sol
  226.                 print(f"  {j}. x={x}, y={y}, a*x={a*x:.1f}, b*y={b*y:.1f}, 总和={a*x + b*y:.1f} {tag}")
  227.             else:
  228.                 a, x, b, y, c, z = sol
  229.                 print(f"  {j}. x={x}, y={y}, z={z}, "
  230.                       f"a*x={a*x:.1f}, b*y={b*y:.1f}, c*z={c*z:.1f}, "
  231.                       f"总和={a*x + b*y + c*z:.1f} {tag}")
  232.  
  233. def run_with_timeout(func, args=(), kwargs=None, timeout=SOLVER_TIMEOUT):
  234.     """运行函数并设置超时限制"""
  235.     if kwargs is None:
  236.         kwargs = {}
  237.  
  238.     result = []
  239.     error = []
  240.  
  241.     def wrapper():
  242.         try:
  243.             result.append(func(*args, **kwargs))
  244.         except Exception as e:
  245.             error.append(e)
  246.  
  247.     thread = threading.Thread(target=wrapper)
  248.     thread.daemon = True
  249.     thread.start()
  250.     thread.join(timeout)
  251.  
  252.     if thread.is_alive():
  253.         print(f"警告: {func.__name__} 超时（{timeout}秒），跳过此方法")
  254.         return None
  255.  
  256.     if error:
  257.         raise error[0]
  258.  
  259.     return result[0]
  260.  
  261. def main():
  262.     print(f"目标值: {TARGET}")
  263.  
  264.     # 生成波动后的系数
  265.     FLUCTUATED_VALUES = [round(v - FLUCTUATION, 1) for v in BASE_VALUES]
  266.  
  267.     # 尝试基础系数
  268.     print(f"\n==== 尝试基础系数 ====")
  269.  
  270.     # 目标值75085 < 259000，会按顺序尝试单、双、三变量解
  271.     base_solutions = {
  272.         'single': run_with_timeout(find_single_variable_solutions, args=(BASE_VALUES,)),
  273.         'two': run_with_timeout(find_two_variable_solutions, args=(BASE_VALUES,)),
  274.         'three': []
  275.     }
  276.  
  277.     has_solution = False
  278.  
  279.     # 显示单变量解
  280.     if base_solutions['single']:
  281.         has_solution = True
  282.         display_solutions({a: [sol] for a, sol in zip(BASE_VALUES, base_solutions['single']) if sol}, 1)
  283.  
  284.     # 显示双变量解
  285.     if base_solutions['two'] and len(base_solutions['two']) > 0:
  286.         has_solution = True
  287.         display_solutions(base_solutions['two'], 2)
  288.  
  289.     # 单变量和双变量都无解时，尝试三变量解
  290.     if not has_solution:
  291.         print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
  292.         base_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(BASE_VALUES,))
  293.  
  294.         if base_solutions['three'] and len(base_solutions['three']) > 0:
  295.             has_solution = True
  296.             display_solutions(base_solutions['three'], 3)
  297.  
  298.     if has_solution:
  299.         print(f"\n使用基础系数列表，共找到有效解")
  300.         return
  301.  
  302.     # 如果基础系数没有找到解，尝试波动系数
  303.     print(f"\n==== 尝试波动系数 ====")
  304.  
  305.     fluctuated_solutions = {
  306.         'single': run_with_timeout(find_single_variable_solutions, args=(FLUCTUATED_VALUES,)),
  307.         'two': run_with_timeout(find_two_variable_solutions, args=(FLUCTUATED_VALUES,)),
  308.         'three': []
  309.     }
  310.  
  311.     has_solution = False
  312.  
  313.     # 显示单变量解
  314.     if fluctuated_solutions['single']:
  315.         has_solution = True
  316.         display_solutions({a: [sol] for a, sol in zip(FLUCTUATED_VALUES, fluctuated_solutions['single']) if sol}, 1)
  317.  
  318.     # 显示双变量解
  319.     if fluctuated_solutions['two'] and len(fluctuated_solutions['two']) > 0:
  320.         has_solution = True
  321.         display_solutions(fluctuated_solutions['two'], 2)
  322.  
  323.     # 单变量和双变量都无解时，尝试三变量解
  324.     if not has_solution:
  325.         print(f"\n==== 单变量和双变量无解，尝试三变量解 ====")
  326.         fluctuated_solutions['three'] = run_with_timeout(find_three_variable_solutions, args=(FLUCTUATED_VALUES,))
  327.  
  328.         if fluctuated_solutions['three'] and len(fluctuated_solutions['three']) > 0:
  329.             has_solution = True
  330.             display_solutions(fluctuated_solutions['three'], 3)
  331.  
  332.     if has_solution:
  333.         print(f"\n使用波动系数列表，共找到有效解")
  334.         return
  335.  
  336.     # 如果所有系数集都没有找到解
  337.     print("\n没有找到符合条件的解，即使使用波动后的系数列表。")
  338.  
  339. if __name__ == "__main__":
  340.     start_time = time.time()
  341.     main()
  342.     print(f"\n总耗时: {time.time() - start_time:.2f}秒")
Success #stdin #stdout 0.07s 11864KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目标值: 241327

==== 尝试基础系数 ====

找到 11 组2变量解：

1. 组合: a=36.5, b=41.5 (3 个有效解)
  1. x=3427, y=2801.0, a*x=125085.5, b*y=116241.5, 总和=241327.0 [平衡解]
  2. x=3925, y=2363.0, a*x=143262.5, b*y=98064.5, 总和=241327.0 [平衡解]
  3. x=4423, y=1925.0, a*x=161439.5, b*y=79887.5, 总和=241327.0 [原始解]

2. 组合: a=36.5, b=68.5 (2 个有效解)
  1. x=3517, y=1649.0, a*x=128370.5, b*y=112956.5, 总和=241327.0 [平衡解]
  2. x=4339, y=1211.0, a*x=158373.5, b*y=82953.5, 总和=241327.0 [平衡解]

3. 组合: a=41.5, b=59 (2 个有效解)
  1. x=2976, y=1997.0, a*x=123504.0, b*y=117823.0, 总和=241327.0 [平衡解]
  2. x=3566, y=1582.0, a*x=147989.0, b*y=93338.0, 总和=241327.0 [平衡解]

4. 组合: a=41.5, b=68.5 (2 个有效解)
  1. x=3326, y=1508.0, a*x=138029.0, b*y=103298.0, 总和=241327.0 [平衡解]
  2. x=4011, y=1093.0, a*x=166456.5, b*y=74870.5, 总和=241327.0 [平衡解]

5. 组合: a=41.5, b=74 (2 个有效解)
  1. x=3226, y=1452.0, a*x=133879.0, b*y=107448.0, 总和=241327.0 [平衡解]
  2. x=3966, y=1037.0, a*x=164589.0, b*y=76738.0, 总和=241327.0 [平衡解]

6. 组合: a=41.5, b=91.5 (1 个有效解)
  1. x=3661, y=977.0, a*x=151931.5, b*y=89395.5, 总和=241327.0 [平衡解]

7. 组合: a=59, b=68.5 (1 个有效解)
  1. x=2437, y=1424.0, a*x=143783.0, b*y=97544.0, 总和=241327.0 [平衡解]

8. 组合: a=59, b=74 (6 个有效解)
  1. x=2081, y=1602, a*x=122779.0, b*y=118548.0, 总和=241327.0 [平衡解]
  2. x=2229, y=1484, a*x=131511.0, b*y=109816.0, 总和=241327.0 [平衡解]
  3. x=2377, y=1366, a*x=140243.0, b*y=101084.0, 总和=241327.0 [原始解]
  4. x=2525, y=1248, a*x=148975.0, b*y=92352.0, 总和=241327.0 [原始解]
  5. x=2673, y=1130, a*x=157707.0, b*y=83620.0, 总和=241327.0 [原始解]

9. 组合: a=59, b=91.5 (1 个有效解)
  1. x=2465, y=1048.0, a*x=145435.0, b*y=95892.0, 总和=241327.0 [平衡解]

10. 组合: a=68.5, b=74 (1 个有效解)
  1. x=2110, y=1308.0, a*x=144535.0, b*y=96792.0, 总和=241327.0 [平衡解]

11. 组合: a=68.5, b=91.5 (4 个有效解)
  1. x=1864, y=1242.0, a*x=127684.0, b*y=113643.0, 总和=241327.0 [平衡解]
  2. x=2047, y=1105.0, a*x=140219.5, b*y=101107.5, 总和=241327.0 [平衡解]
  3. x=2230, y=968.0, a*x=152755.0, b*y=88572.0, 总和=241327.0 [原始解]
  4. x=2413, y=831.0, a*x=165290.5, b*y=76036.5, 总和=241327.0 [原始解]

使用基础系数列表，共找到有效解

总耗时: 0.01秒
https://ideone.com/5VykYa
language:
Python 3 nbc (python 3.7.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!