fork(1) 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 =80082  # 目标值
  10. BASE_VALUES = [38.5,44,61,70.5,75.5,93]  # 基础系数列表
  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.06s 11608KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
目标值: 80082

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

找到 12 组2变量解：

1. 组合: a=38.5, b=70.5 (8 个有效解)
  1. x=855, y=669.0, a*x=32917.5, b*y=47164.5, 总和=80082.0 [平衡解]
  2. x=573, y=823.0, a*x=22060.5, b*y=58021.5, 总和=80082.0 [平衡解]
  3. x=9, y=1131.0, a*x=346.5, b*y=79735.5, 总和=80082.0 [原始解]
  4. x=291, y=977.0, a*x=11203.5, b*y=68878.5, 总和=80082.0 [原始解]
  5. x=1137, y=515.0, a*x=43774.5, b*y=36307.5, 总和=80082.0 [原始解]

2. 组合: a=38.5, b=75.5 (7 个有效解)
  1. x=623, y=743.0, a*x=23985.5, b*y=56096.5, 总和=80082.0 [平衡解]
  2. x=925, y=589.0, a*x=35612.5, b*y=44469.5, 总和=80082.0 [平衡解]
  3. x=19, y=1051.0, a*x=731.5, b*y=79350.5, 总和=80082.0 [原始解]
  4. x=321, y=897.0, a*x=12358.5, b*y=67723.5, 总和=80082.0 [原始解]
  5. x=1227, y=435.0, a*x=47239.5, b*y=32842.5, 总和=80082.0 [原始解]

3. 组合: a=44, b=61 (30 个有效解)
  1. x=747, y=774, a*x=32868.0, b*y=47214.0, 总和=80082.0 [平衡解]
  2. x=808, y=730, a*x=35552.0, b*y=44530.0, 总和=80082.0 [平衡解]
  3. x=15, y=1302, a*x=660.0, b*y=79422.0, 总和=80082.0 [原始解]
  4. x=76, y=1258, a*x=3344.0, b*y=76738.0, 总和=80082.0 [原始解]
  5. x=137, y=1214, a*x=6028.0, b*y=74054.0, 总和=80082.0 [原始解]

4. 组合: a=44, b=70.5 (13 个有效解)
  1. x=660, y=724.0, a*x=29040.0, b*y=51042.0, 总和=80082.0 [平衡解]
  2. x=801, y=636.0, a*x=35244.0, b*y=44838.0, 总和=80082.0 [平衡解]
  3. x=96, y=1076.0, a*x=4224.0, b*y=75858.0, 总和=80082.0 [原始解]
  4. x=237, y=988.0, a*x=10428.0, b*y=69654.0, 总和=80082.0 [原始解]
  5. x=378, y=900.0, a*x=16632.0, b*y=63450.0, 总和=80082.0 [原始解]

5. 组合: a=44, b=75.5 (12 个有效解)
  1. x=715, y=644.0, a*x=31460.0, b*y=48622.0, 总和=80082.0 [平衡解]
  2. x=564, y=732.0, a*x=24816.0, b*y=55266.0, 总和=80082.0 [平衡解]
  3. x=111, y=996.0, a*x=4884.0, b*y=75198.0, 总和=80082.0 [原始解]
  4. x=262, y=908.0, a*x=11528.0, b*y=68554.0, 总和=80082.0 [原始解]
  5. x=413, y=820.0, a*x=18172.0, b*y=61910.0, 总和=80082.0 [原始解]

6. 组合: a=44, b=93 (20 个有效解)
  1. x=573, y=590, a*x=25212.0, b*y=54870.0, 总和=80082.0 [平衡解]
  2. x=666, y=546, a*x=29304.0, b*y=50778.0, 总和=80082.0 [平衡解]
  3. x=15, y=854, a*x=660.0, b*y=79422.0, 总和=80082.0 [原始解]
  4. x=108, y=810, a*x=4752.0, b*y=75330.0, 总和=80082.0 [原始解]
  5. x=201, y=766, a*x=8844.0, b*y=71238.0, 总和=80082.0 [原始解]

7. 组合: a=61, b=70.5 (9 个有效解)
  1. x=624, y=596.0, a*x=38064.0, b*y=42018.0, 总和=80082.0 [平衡解]
  2. x=483, y=718.0, a*x=29463.0, b*y=50619.0, 总和=80082.0 [平衡解]
  3. x=60, y=1084.0, a*x=3660.0, b*y=76422.0, 总和=80082.0 [原始解]
  4. x=201, y=962.0, a*x=12261.0, b*y=67821.0, 总和=80082.0 [原始解]
  5. x=342, y=840.0, a*x=20862.0, b*y=59220.0, 总和=80082.0 [原始解]

8. 组合: a=61, b=75.5 (8 个有效解)
  1. x=590, y=584.0, a*x=35990.0, b*y=44092.0, 总和=80082.0 [平衡解]
  2. x=439, y=706.0, a*x=26779.0, b*y=53303.0, 总和=80082.0 [平衡解]
  3. x=137, y=950.0, a*x=8357.0, b*y=71725.0, 总和=80082.0 [原始解]
  4. x=288, y=828.0, a*x=17568.0, b*y=62514.0, 总和=80082.0 [原始解]
  5. x=741, y=462.0, a*x=45201.0, b*y=34881.0, 总和=80082.0 [原始解]

9. 组合: a=61, b=93 (14 个有效解)
  1. x=549, y=501, a*x=33489.0, b*y=46593.0, 总和=80082.0 [平衡解]
  2. x=456, y=562, a*x=27816.0, b*y=52266.0, 总和=80082.0 [平衡解]
  3. x=84, y=806, a*x=5124.0, b*y=74958.0, 总和=80082.0 [原始解]
  4. x=177, y=745, a*x=10797.0, b*y=69285.0, 总和=80082.0 [原始解]
  5. x=270, y=684, a*x=16470.0, b*y=63612.0, 总和=80082.0 [原始解]

10. 组合: a=70.5, b=75.5 (8 个有效解)
  1. x=503, y=591.0, a*x=35461.5, b*y=44620.5, 总和=80082.0 [平衡解]
  2. x=654, y=450.0, a*x=46107.0, b*y=33975.0, 总和=80082.0 [平衡解]
  3. x=50, y=1014.0, a*x=3525.0, b*y=76557.0, 总和=80082.0 [原始解]
  4. x=201, y=873.0, a*x=14170.5, b*y=65911.5, 总和=80082.0 [原始解]
  5. x=352, y=732.0, a*x=24816.0, b*y=55266.0, 总和=80082.0 [原始解]

11. 组合: a=70.5, b=93 (19 个有效解)
  1. x=508, y=476.0, a*x=35814.0, b*y=44268.0, 总和=80082.0 [平衡解]
  2. x=446, y=523.0, a*x=31443.0, b*y=48639.0, 总和=80082.0 [平衡解]
  3. x=12, y=852.0, a*x=846.0, b*y=79236.0, 总和=80082.0 [原始解]
  4. x=74, y=805.0, a*x=5217.0, b*y=74865.0, 总和=80082.0 [原始解]
  5. x=136, y=758.0, a*x=9588.0, b*y=70494.0, 总和=80082.0 [原始解]

12. 组合: a=75.5, b=93 (6 个有效解)
  1. x=414, y=525.0, a*x=31257.0, b*y=48825.0, 总和=80082.0 [平衡解]
  2. x=600, y=374.0, a*x=45300.0, b*y=34782.0, 总和=80082.0 [平衡解]
  3. x=42, y=827.0, a*x=3171.0, b*y=76911.0, 总和=80082.0 [原始解]
  4. x=228, y=676.0, a*x=17214.0, b*y=62868.0, 总和=80082.0 [原始解]
  5. x=786, y=223.0, a*x=59343.0, b*y=20739.0, 总和=80082.0 [原始解]

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

总耗时: 0.01秒
https://ideone.com/zyzeY5
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!