Форум программистов, компьютерный форум, киберфорум
Наши страницы
Assembler для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
1

Найти наиболее часто встречающееся в массиве число

19.11.2015, 20:36. Просмотров 1064. Ответов 12
Метки нет (Все метки)

Доброго времени суток, есть массив целых чисел, как найти наиболее часто встречающееся число? Помогите плз.
Assembler
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
.model small
.stack 100h
.data
    massiv dw 80 dup(?)
    msg1   db 'Vvodite elementi massiva: $'
    msg2   db 'Massiv:$'
.code
start:
    mov ax,@data
    mov ds,ax
    mov ah,09h
    lea dx,msg1
    int 21h
    xor dx,dx
input_loop:
    mov ah,01h
    int 21h
    cmp al,0dh
    je number
    mov cl,al
    mov ax,dx
    xor ch,ch
    add ax,cx
    mov dx,ax
    jmp input_loop
number:
    mov bx,cx
    shl bx,1
    mov massiv[bx],dx
    inc cx
    jmp cont
cont:
    xor dx,dx
    cmp cx, 30
    je output
    cmp al,0dh
    je output
    jmp input_loop
output:  
    mov dx, massiv[bx]
    cmp dx, 0h
    je exit
exit:
    mov ah,4ch
    int 21h
end start
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.11.2015, 20:36
Ответы с готовыми решениями:

Наиболее часто повторяющаяся цифра (символ)
Здравствуйте! Вроде, подобного примера не встречала: "Среди цифр введённой строки распечатать ту,...

Определить наиболее часто встречающийся символ в файле
Всем вечер добрый , нужна помощь помогите кто может : Определить в файле наиболее часто...

Определить наиболее часто встречающийся символ в файле
Условие такое: Дан файл, содержащий текст. Определить наиболее часто встречающуюся в нем букву...

Найти беззнаковое число наиболее близкое к заданному
Напишите пожалуйста программу на Ассемблере. Вот задание: Найти беззнаковое число наиболее близкое...

Найти число наиболее близкое к заданному для массива 8-разрядных чисел со знаком
Помогите, найти ошибку) format PE console ; 32-разрядная консольная...

12
Hadros
36 / 36 / 17
Регистрация: 12.04.2012
Сообщений: 165
22.11.2015, 06:37 2
Лучший ответ Сообщение было отмечено llch как решение

Решение

Простой вариант. R1, R2, ..., Ri1, ... - регистры или переменные.
R1 - число.
R2 - счётчик, сколько раз это число встречается в массиве.
R3 - старое число
R4 - старый счётчик, изначально устанавливается в 0

1) И вот, цикл по индексу массива от начала до (конца-1). Индекс в регистре Ri1.
2) Элемент массива с индексом Ri1 заносится в R1, а счётчик R2 устанавливается в единицу.
3) Внутренний цикл по индексу массива от (Ri1+1) до конца. Индекс в регистре Ri2.
4) Если элемент массива с индексом Ri2 равен числу R1, то увеличить счётчик R2.
5) Крутить внутренний цикл
6) Если счётчик R2 больше счётчика R4, то: переместить R2 в R4 и переместить R1 в R3
7) Если значение (<индекс последнего элемента массива> минус индекс Ri1) меньше счётчика R4, то можно преждевременно закончить внешний цикл и перейти к пункту 9.
8) Крутить внешний цикл
9) Теперь в R3 лежит число, которое встречается в массиве R4 раз, и это ответ

Добавлено через 9 минут
Седьмой пункт необязательный, можно без него
1
Mikl___
Автор FAQ
14127 / 6618 / 686
Регистрация: 11.11.2010
Сообщений: 11,901
22.11.2015, 07:48 3
Еще вариант:
сортируем числа в массиве по увеличению (уменьшению), повторяющиеся числа оказываются рядом и их не сложно подсчитать и выяснить какое из чисел повторяется наиболее часто
0
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
30.11.2015, 00:51  [ТС] 4
Hadros, сделал по вашему алгоритму, как понимаю, если не затруднит пожалуйста помогите привести в рабочее состояние:
Assembler
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
.model small
.stack 100h
.data
msg1    db  'Enter array: $'
msg2    db  'Array: $'
array   db  1,1,5,3,6,3,7,3
.code
main:
    mov ax,@data
    mov ds,ax
    xor ax,ax
    
    mov si,0        ; Устанавливаю индексы
    mov di,si       
    mov cl,0        ; Старый счётчик
    mov bl,0        ; Счётчик, сколько раз число встречается в массиве
    mov cx,7        
First:
    mov dx,cx
    mov cx,7  
    mov al,array[si]    ; Элемент массива с индексом si заносится в al
    inc bl      ; Счётчик устанавливается в единицу
Second: 
    cmp al,array[di+1]  ; Если элемент массива с индексом di+1 равен числу al, то увеличиваем счётчик bl
    je A
Third:
    loop Second     ; Внутренний цикл
    xor di,di       
    cmp bl,cl       ; Если счетчик bl больше cl, то перемещаем bl в cl и al в ah
    jg B
Fourth:    
    inc si      ; Увеличиваем индекс si на единицу
    xor bl,bl       ; Обнуляем счётчик bl
    mov cx,dx       
    loop First      ; Внешний цикл
    jmp Output
A:  
    inc bl
    jmp Third        
B:
    mov cl,bl
    mov ah,al
    jmp Fourth
Output:
    mov dl,ah
    add al,30h
    mov ah,02h
    int 21h
    jmp Exit
Exit:
    mov ax,4c00h
    int 21h
end main
0
30.11.2015, 00:51
Hadros
36 / 36 / 17
Регистрация: 12.04.2012
Сообщений: 165
30.11.2015, 03:00 5
llch, во внутреннем цикле di должен меняться. Это же индекс в массиве. У вас там 7 раз сравнивается одна и та же пара элементов

Добавлено через 3 минуты
Использовать CL для "старого счётчика" и одновременно CX для организации цикла не прокатит. После 17-й строки в CL окажется семёрка. Если регистров не хватает, используйте переменные в памяти для "старого счётчика". А ещё, есть PUSH и POP.

Добавлено через 16 минут
Если у вас массив небольшой (до 256 элементов), то свободна старшая часть регистра DX. Можно использовать её (DH) для хранения "старого счётчика". А состояние внешнего цикла сохранять не в DX, а в DL.
1
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
30.11.2015, 11:19  [ТС] 6
Hadros, спасибо все работает вроде. еще один глупый вопрос..) в данном случае у меня вместо числа 3 выводится сердечко, как сделать что бы выводилось число?
Assembler
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
.model small
.stack 100h
.data
msg1    db  'Array: $'
array   db  1,1,5,3,6,3,7,3
i       dw  0
.code
main:
    mov ax,@data
    mov ds,ax
    xor ax,ax
    mov dh,0
    mov si,0        ; Устанавливаю индексы
    mov di,si       
    mov cl,0        ; Старый счётчик
    mov bl,0        ; Счётчик, сколько раз число встречается в массиве
    mov cx,7        
First:
    mov i,cx
    mov cx,7  
    mov al,array[si]    ; Элемент массива с индексом si заносится в al
    inc bl      ; Счётчик устанавливается в единицу
Second: 
    cmp al,array[di+1]  ; Если элемент массива с индексом di+1 равен числу al, то увеличиваем счётчик bl
    je A
    inc di
Third:
    loop Second     ; Внутренний цикл
    xor di,di       
    cmp bl,cl       ; Если счетчик bl больше cl, то перемещаем bl в cl и al в ah
    jg B
Fourth:    
    inc si      ; Увеличиваем индекс si на единицу
    mov di,si
    xor bl,bl       ; Обнуляем счётчик bl
    mov cx,i        
    loop First      ; Внешний цикл
    jmp Output
A:  
    inc bl
    jmp Third        
B:
    mov cl,bl
    mov ah,al
    jmp Fourth
Output:
    mov dl,ah
    add al,30h
    mov ah,02h
    int 21h
    jmp Exit
Exit:
    mov ax,4c00h
    int 21h
end main
0
Mikl___
Автор FAQ
14127 / 6618 / 686
Регистрация: 11.11.2010
Сообщений: 11,901
30.11.2015, 11:42 7
Цитата Сообщение от llch Посмотреть сообщение
в данном случае у меня вместо числа 3 выводится сердечко, как сделать что бы выводилось число?
Перед выводом цифры на экран добавить код "0". Должно быть вот так
Assembler
1
2
3
4
5
Output:
    mov dl,ah
    add dl,30h <--- Должно быть вот так
    mov ah,2
    int 21h
1
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
02.12.2015, 23:45  [ТС] 8
Гайс, снова нид хелп, вообщем преподаватель сказал нужно еще учесть момент с повторением чисел, т.е. если например в массиве есть число 2 и число 4 которые повторяются по 2 раза, нужно вывести их оба. Вообщем как я понимаю нужно сделать еще один массив, куда мы будет закидывать наши числа (вместо ah), по условию jge(больше или равно), когда сравниваем текущий счётчик со старым, вот набросал код как понимаю, но где-то ошибка.
Assembler
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
.model small
.stack 100h
.data
array   db  8   dup (0)
array2  db  8   dup (?) 
msg1    db  'Enter array: $'
msg2    db  10,13,'Array: $'
msg3    db  10,13,'The most repeated number in array: $' 
i       dw  0
o       db  0
.code
main:
    mov ax,@data
    mov ds,ax
    xor ax,ax
    mov cx,8
    mov si,0
    lea dx,msg1
    mov ah,09h
    int 21h
InputArray:
    mov ah,01h
    mov al,00h
    int 21h
    sub al,30h
    mov array[si],al
    inc si
    loop InputArray
    
    lea dx,msg2
    mov ah,09h
    int 21h
    
    mov cx,8
    xor si,si
OutputArray:
    mov ah,02h
    mov dl,array[si]
    add dl,30h
    int 21h
    inc si
    loop OutputArray
    
    mov bl,0
    mov dh,0
    xor si,si
    mov cx,7
First:      
    mov i,cx
    mov al,array[si]
    inc bl
    push si
Second:
    cmp al,array[si+1]
    je A 
    inc si
Third:
    loop Second
    cmp bl,dh
    jge B        
Fourth: 
    pop si
    inc si
    xor bl,bl
    mov cx,i
    loop First
    jmp Output
A:
    inc bl
    jmp Third
B:
    mov dh,bl
    mov array2[di],al
    inc di
    jmp Fourth         
Output:
    lea dx,msg3
    mov ah,09h
    int 21h
    mov cx,8
OutputArray2:
    mov ah,02h
    mov dl,array2[di]
    add dl,30h
    int 21h
    inc di
    loop OutputArray2
    jmp Exit    
Exit:
     mov ax,4c00h
     int 21h
end main
0
Hadros
36 / 36 / 17
Регистрация: 12.04.2012
Сообщений: 165
03.12.2015, 00:15 9
llch, а этот вариант вообще правильно работает? Вроде бы ошибка: между строками 68..70 не хватает увеличения SI. У меня негде проверить 16-битный код, только если переписывать.
Цитата Сообщение от llch Посмотреть сообщение
Вообщем как я понимаю нужно сделать еще один массив, куда мы будет закидывать наши числа
Наверное, лучше сделать второй массив размером в 256 элементов. Изначально заполнить его нулями, и, когда в первом массиве встречается число N, то добавлять единичку к array2[N]. Для этого достаточно одного цикла по элементам первого массива.

На втором этапе нужно будет найти все самые большие элементы второго массива. Ответом к заданию будут индексы этих элементов.
0
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
03.12.2015, 00:57  [ТС] 10
Hadros, угу, с inc si мальца затупил, поправил, но код не пашет все равно. Про ваш вариант немного не понял, если можно поподробней, спс.
Assembler
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
.model small
.stack 100h
.data
array   db  8   dup (0)
array2  db  8   dup (?) 
msg1    db  'Enter array: $'
msg2    db  10,13,'Array: $'
msg3    db  10,13,'The most repeated number in array: $' 
i       dw  0
o       db  0
.code
main:
    mov ax,@data
    mov ds,ax
    xor ax,ax
    mov cx,8
    mov si,0
    lea dx,msg1
    mov ah,09h
    int 21h
InputArray:
    mov ah,01h
    mov al,00h
    int 21h
    sub al,30h
    mov array[si],al
    inc si
    loop InputArray
    
    lea dx,msg2
    mov ah,09h
    int 21h
    
    mov cx,8
    xor si,si
OutputArray:
    mov ah,02h
    mov dl,array[si]
    add dl,30h
    int 21h
    inc si
    loop OutputArray
    
    mov bl,0
    mov dh,0
    xor si,si
    mov cx,7
First:      
    mov i,cx
    mov al,array[si]
    inc bl
    push si
Second:
    cmp al,array[si+1]
    je A
Third:
    loop Second
    cmp bl,dh
    jge B        
Fourth: 
    pop si
    inc si
    xor bl,bl
    mov cx,i
    loop First
    jmp Output
A:
    inc bl
    inc si
    jmp Third
B:
    mov dh,bl
    mov array2[di],al
    inc di
    jmp Fourth         
Output:
    lea dx,msg3
    mov ah,09h
    int 21h
    mov cx,8
OutputArray2:
    mov ah,02h
    mov dl,array2[di]
    add dl,30h
    int 21h
    inc di
    loop OutputArray2
    jmp Exit    
Exit:
     mov ax,4c00h
     int 21h
end main
0
Hadros
36 / 36 / 17
Регистрация: 12.04.2012
Сообщений: 165
03.12.2015, 01:29 11
Цитата Сообщение от llch Посмотреть сообщение
если можно поподробней
Числа в первом массиве, как я понял, могут быть от 0 до 255. Второй массив - это количество раз, которое какое-нибудь число встречается в первом массиве. Чисел всего 256, и во втором массиве 256 элементов. Первым этапом вы подсчитываете, сколько раз каждое число встречается в первом массиве. Допустим, если первый массив такой:
1 33 7 33 0 17 33 2 2 2
то во втором массиве следующие элементы будут после первого этапа иметь значения:
array2[0]=1
array2[1]=1
array2[2]=3
array2[7]=1
array2[17]=1
array2[33]=3
все остальные элементы array2 будут нулями

Второй этап: найти все самые большие элементы второго массива. В моём примере - это элементы с индексами 2 и 33. Значение этих элементов равно 3. Все остальные элементы меньше трёх.

Ответ к заданию: 2, 33

Добавлено через 10 минут
Цитата Сообщение от llch Посмотреть сообщение
поправил, но код не пашет все равно
Так вы зачем убрали "inc si" из 56-ой строки в #8? SI должно увеличиваться во внутреннем цикле всегда, независимо от того, какой будет результат сравнения "cmp al,array[si+1]"
0
llch
0 / 0 / 0
Регистрация: 04.05.2014
Сообщений: 15
03.12.2015, 02:53  [ТС] 12
Hadros, да, сорри, но это снова не решило проблему, вместо чисел выводятся в основном одни нули и какие-то буквы в конце.
Кликните здесь для просмотра всего текста
Assembler
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
.model small
.stack 100h
.data
array   db  8   dup (0)
array2  db  8   dup (?) 
msg1    db  'Enter array: $'
msg2    db  10,13,'Array: $'
msg3    db  10,13,'The most repeated number in array: $' 
i       dw  0
o       db  0
.code
main:
    mov ax,@data
    mov ds,ax
    xor ax,ax
    mov cx,8
    mov si,0
    lea dx,msg1
    mov ah,09h
    int 21h
InputArray:
    mov ah,01h
    mov al,00h
    int 21h
    sub al,30h
    mov array[si],al
    inc si
    loop InputArray
    
    lea dx,msg2
    mov ah,09h
    int 21h
    
    mov cx,8
    xor si,si
OutputArray:
    mov ah,02h
    mov dl,array[si]
    add dl,30h
    int 21h
    inc si
    loop OutputArray
    
    mov bl,0
    mov dh,0
    xor si,si
    mov cx,7
First:      
    mov i,cx
    mov al,array[si]
    inc bl
    push si
Second:
    cmp al,array[si+1]
    je A
    inc si
Third:
    loop Second
    cmp bl,dh
    jge B        
Fourth: 
    pop si
    inc si
    xor bl,bl
    mov cx,i
    loop First
    jmp Output
A:
    inc bl
    inc si
    jmp Third
B:
    mov dh,bl
    mov array2[di],al
    inc di
    jmp Fourth         
Output:
    lea dx,msg3
    mov ah,09h
    int 21h
    mov cx,8
OutputArray2:
    mov ah,02h
    mov dl,array2[di]
    add dl,30h
    int 21h
    inc di
    loop OutputArray2
    jmp Exit    
Exit:
     mov ax,4c00h
     int 21h
end main
0
Hadros
36 / 36 / 17
Регистрация: 12.04.2012
Сообщений: 165
03.12.2015, 08:19 13
llch, Работающий код для x64. Тут надо заменить названия регистров и, наверное, подправить адресацию. У меня для исправления адресации недостаточно знаний и проверять негде.
Assembler
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
      // Адрес массива с ответами пусть изначально лежит в стеке
      // RSI - адрес исходного массива, затем адрес массива с ответами
      // RDI - адрес второго массива (временного)
      // RAX - номер максимального элемента исходного массива, затем размер ответа
 
      // Подсчёт того, сколько раз каждое число встречается в первом массиве
      xor     rdx,rdx         // Индекс в исходном массиве, адрес начала массива уже находится в RSI
      xor     rcx,rcx         // Обнуление старшей части регистра RCX, - понадобится сейчас для адресации
  @loop1:
      mov     cl,[rsi+rdx]    // В CL число из первого массива по индексу [RSI]
      add     [rdi+rcx],1     // Само это число используется как индекс во втором массиве. Старшая часть RCX обнулена ранее.
      inc     rdx             // Следующий индекс исходного массива
      cmp     rdx,rax         // Всего в исходном массиве (RAX+1) элемент: от 0 до RAX
      jbe     @loop1
 
      // Поиск самого большого числа во втором массиве
      mov     rdx,1           // Индекс во втором массиве, адрес начала массива всё ещё находится в RDI
      mov     bl,[rdi]        // В BL будет максимальное число. Изначально там нулевое число второго массива.
  @loop2:
      mov     cl,[rdi+rdx]    // Проверяемое число второго массива
      cmp     bl,cl           // Сравнивается с максимальным
      cmovb   rbx,rcx         // Если оно больше, то сохраняется в BL. Старшая часть RCX по-прежнему обнулена.
      inc     rdx             // Следующий индекс второго массива
      cmp     rdx,255         // Всего во втором массиве 256 элементов: от 0 до 255
      jbe     @loop2
 
      // Поиск индексов всех самых больших чисел второго массива. В BL уже находится самое большое число.
      pop     rsi             // Адрес массива с ответами восстановлен из стека
      xor     rax,rax         // Количество чисел в ответе. Изначально ноль.
      xor     rdx,rdx         // Индекс во втором массиве, адрес начала второго массива по-прежнему лежит в RDI
  @loop3:
      cmp     bl,[rdi+rdx]    // Поиск всех чисел второго массива, равных BL
      je      @save_result
      inc     rdx             // следующий индекс второго массива
      cmp     rdx,255         // всего во втором массиве 256 элементов: от 0 до 255
      jbe     @loop3
      jmp     @done
  @save_result:
      mov     [rsi+rax],dl    // Сохранение найденного в массив ответов
      inc     rax             // Увеличение индекса в массиве ответов
      inc     rdx             // следующий индекс второго массива
      cmp     rdx,255         // всего во втором массиве 256 элементов: от 0 до 255
      jbe     @loop3
  @done:
После выполнения кода в массиве с ответами будут ответы, а количество чисел в этом массиве будет в регистре RAX (или AX).
RSI, RDI и RAX надо заполнить перед этим кодом. И адрес массива для ответов в стек положить. Или не класть, но тогда в 28-й строке загрузить его в RSI или куда там обычно загружают.
1
03.12.2015, 08:19
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2015, 08:19

Найти Наиболее Часто Встречающееся Число в Массиве
Помогите пожалуйста решить задачку на VBA Вот условие : В массиве целых чисел (одномерном)...

Найти в массиве наиболее часто встречающееся число
Найти в массиве наиболее часто встречающееся число. Если таких чисел несколько, определить...

найти наиболее часто встречающееся число в массиве
В массиве целых чисел с количеством элементов n найти наиболее часто встречающееся число. Если...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.