Bonjour a tous,
J'ai le probleme suivant auquel je ne trouve pas de solution optimale. Je cherche a trouver a partir de nombres arbitraires (ie: 1, 3, 6, 7, 14, ...) un nombre final (ie: 21). Je peux seulement ajouter les nombres entres eux, mais les nombres peuvent etre utilises plusieurs fois.
Dans les nombres proposes au dessus, pour trouver 21, je peux faire:
- 7 + 14 = 21
- 7 * 3 = 7 + 7 + 7 = 21
- 3 * 7 = 3 + 3 + 3 + 3 + 3 + 3 + 3 = 21
- 3 * 2 + 7 * 2 + 1 = 3 + 3 + 7+ 7 + 1 = 21
- ...
Je cherche a trouver la solution qui implique le moins d'operations d'additions. Les solutions les meilleurs sont dans l'ordre 1, 2, 4, puis 3.
Je vois pas trop comment approcher le probleme. Je pense que c'est une equation a n inconnues (ie: a + 3b +6c + 7d + 14e + ... = 21) ou je n'ai qu'une seule equation et ou chaque variable peut etre nulle. Y'a-t-il un moyen d'essayer de resoudre ca dans certains cas?
J'imagine que s'il y a plusieurs solutions, la solution optimale sera celle ou la somme des variables sera la plus petite, indiquant le moins d'operations.
Merci
PS: Pour ceux que ca interesse, voila comment sont trouves les nombres:
et un exemple de sortie:
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60 #!/usr/bin/env python # -*- coding:utf-8 -*- from __future__ import print_function from elftools.elf.elffile import ELFFile from elftools.common.exceptions import ELFError, ELFParseError from struct import unpack, error from sys import argv, stderr names = (b".text", b".data") sections = [] segments = [] if len(argv) != 3: print("Usage: %s filename number" % argv[0]) exit(-1) try: f = open(argv[1], "rb") except Exception as ex: print("Can't open file %s: %s" % (argv[1], ex), file=stderr) exit(-1) try: elf = ELFFile(f) except (ELFError, ELFParseError) as ex: print("Failed to parse elf file %s: %s" % (argv[1], ex), file=stderr) exit(-1) for s in names: try: section = elf.get_section_by_name(s) if section != None: sections.append(section) except (ELFError, ELFParseError) as ex: print("Failed to parse elf file %s: %s" % (argv[1], ex), file=stderr) for segment in elf.iter_segments(): for section in sections: if segment.section_in_segment(section) and (segment["p_type"] == "PT_LOAD"): segments.append(segment) print("Found loadable segment starting at [address 0x%08x, offset 0x%08x]" % (segment["p_vaddr"], segment["p_offset"])) candidates = {} for segment in segments: segment_data = segment.data() for i in xrange(0, len(segment_data)): try: num = unpack("<I", segment_data[i:i+4]) except error as se: print("Reaching end of segment data. Skipping last bytes...", file=stderr) if (num[0] <= int(argv[2])) and (num[0] != 0): candidates[segment["p_vaddr"] + i] = num[0] f.close() for k,v in candidates.iteritems(): print("0x%08x => 0x%08x, %i" % (k, v, v))
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12 dahtah@kali:~$ ./find_numbers.py binary 1234 2> /dev/null | head Found loadable segment starting at [address 0x08048000, offset 0x00000000] Found loadable segment starting at [address 0x08049ed0, offset 0x00000ed0] 0x08049f44 => 0x00000014, 20 0x08048203 => 0x00000010, 16 0x08048005 => 0x00000101, 257 0x08048006 => 0x00000001, 1 0x08048a07 => 0x0000004f, 79 0x08048aa8 => 0x00000003, 3 0x08048013 => 0x00000100, 256 0x08048014 => 0x00000001, 1
Partager