Шарики(задача по программированию) / C++

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)

18 сообщений из 93, страница 4 из 4

все

Шарики(задача по программированию)

#39195759

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglПриврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6
у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13.

...

Рейтинг:

0 / 0

18.03.2016, 19:37

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39195770

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Вы действительно хотите это видеть??
AM

Код: pascal

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.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.

0000002c <__Z10match_backRSt6vectorIiSaIiEEi>:
  2c:	53                   	push   ebx
  2d:	83 ec 18             	sub    esp,0x18
  30:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  34:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
  3b:	00 
  3c:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
  43:	00 
  44:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
  4b:	e8 00 00 00 00       	call   50 <__Z10match_backRSt6vectorIiSaIiEEi+0x24>
  50:	8b 13                	mov    edx,DWORD PTR [ebx]
  52:	8b 43 04             	mov    eax,DWORD PTR [ebx+0x4]
  55:	29 d0                	sub    eax,edx
  57:	c1 f8 02             	sar    eax,0x2
  5a:	83 f8 01             	cmp    eax,0x1
  5d:	76 0a                	jbe    69 <__Z10match_backRSt6vectorIiSaIiEEi+0x3d>
  5f:	8b 4c 82 fc          	mov    ecx,DWORD PTR [edx+eax*4-0x4]
  63:	3b 4c 24 24          	cmp    ecx,DWORD PTR [esp+0x24]
  67:	74 07                	je     70 <__Z10match_backRSt6vectorIiSaIiEEi+0x44>
  69:	31 c0                	xor    eax,eax
  6b:	83 c4 18             	add    esp,0x18
  6e:	5b                   	pop    ebx
  6f:	c3                   	ret    
  70:	3b 4c 82 f8          	cmp    ecx,DWORD PTR [edx+eax*4-0x8]
  74:	0f 94 c0             	sete   al
  77:	83 c4 18             	add    esp,0x18
  7a:	5b                   	pop    ebx
  7b:	c3                   	ret    

0000007c <__Z10erase_backRSt6vectorIiSaIiEEi>:
  7c:	57                   	push   edi
  7d:	56                   	push   esi
  7e:	53                   	push   ebx
  7f:	83 ec 10             	sub    esp,0x10
  82:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  86:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
  8d:	00 
  8e:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
  95:	00 
  96:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
  9d:	e8 00 00 00 00       	call   a2 <__Z10erase_backRSt6vectorIiSaIiEEi+0x26>
  a2:	8b 0b                	mov    ecx,DWORD PTR [ebx]
  a4:	8b 53 04             	mov    edx,DWORD PTR [ebx+0x4]
  a7:	89 d0                	mov    eax,edx
  a9:	29 c8                	sub    eax,ecx
  ab:	c1 f8 02             	sar    eax,0x2
  ae:	74 30                	je     e0 <__Z10erase_backRSt6vectorIiSaIiEEi+0x64>
  b0:	8b 7c 81 fc          	mov    edi,DWORD PTR [ecx+eax*4-0x4]
  b4:	31 c0                	xor    eax,eax
  b6:	3b 7c 24 24          	cmp    edi,DWORD PTR [esp+0x24]
  ba:	75 13                	jne    cf <__Z10erase_backRSt6vectorIiSaIiEEi+0x53>
  bc:	83 ea 04             	sub    edx,0x4
  bf:	40                   	inc    eax
  c0:	89 d6                	mov    esi,edx
  c2:	29 ce                	sub    esi,ecx
  c4:	c1 fe 02             	sar    esi,0x2
  c7:	75 0f                	jne    d8 <__Z10erase_backRSt6vectorIiSaIiEEi+0x5c>
  c9:	8d 76 00             	lea    esi,[esi+0x0]
  cc:	89 53 04             	mov    DWORD PTR [ebx+0x4],edx
  cf:	83 c4 10             	add    esp,0x10
  d2:	5b                   	pop    ebx
  d3:	5e                   	pop    esi
  d4:	5f                   	pop    edi
  d5:	c3                   	ret    
  d6:	66 90                	xchg   ax,ax
  d8:	39 7c b1 fc          	cmp    DWORD PTR [ecx+esi*4-0x4],edi
  dc:	75 ee                	jne    cc <__Z10erase_backRSt6vectorIiSaIiEEi+0x50>
  de:	eb dc                	jmp    bc <__Z10erase_backRSt6vectorIiSaIiEEi+0x40>
  e0:	31 c0                	xor    eax,eax
  e2:	83 c4 10             	add    esp,0x10
  e5:	5b                   	pop    ebx
  e6:	5e                   	pop    esi
  e7:	5f                   	pop    edi
  e8:	c3                   	ret    


00000000 <_main>:
   0:	8d 4c 24 04          	lea    ecx,[esp+0x4]
   4:	83 e4 f0             	and    esp,0xfffffff0
   7:	ff 71 fc             	push   DWORD PTR [ecx-0x4]
   a:	55                   	push   ebp
   b:	89 e5                	mov    ebp,esp
   d:	51                   	push   ecx
   e:	81 ec 24 01 00 00    	sub    esp,0x124
  14:	c7 85 0c ff ff ff 00 	mov    DWORD PTR [ebp-0xf4],0x0
  1b:	00 00 00 
  1e:	c7 85 10 ff ff ff 00 	mov    DWORD PTR [ebp-0xf0],0x0
  25:	00 00 00 
  28:	8d 45 f8             	lea    eax,[ebp-0x8]
  2b:	89 85 14 ff ff ff    	mov    DWORD PTR [ebp-0xec],eax
  31:	c7 85 18 ff ff ff 4c 	mov    DWORD PTR [ebp-0xe8],0x24c
  38:	02 00 00 
  3b:	89 a5 1c ff ff ff    	mov    DWORD PTR [ebp-0xe4],esp
  41:	8d 95 f4 fe ff ff    	lea    edx,[ebp-0x10c]
  47:	89 14 24             	mov    DWORD PTR [esp],edx
  4a:	e8 00 00 00 00       	call   4f <_main+0x4f>
  4f:	e8 00 00 00 00       	call   54 <_main+0x54>
  54:	8d 85 2b ff ff ff    	lea    eax,[ebp-0xd5]
  5a:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
  5e:	c7 04 24 02 00 00 00 	mov    DWORD PTR [esp],0x2
  65:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
  6c:	ff ff ff 
  6f:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
  75:	e8 00 00 00 00       	call   7a <_main+0x7a>
  7a:	83 ec 08             	sub    esp,0x8
  7d:	c7 44 24 04 08 00 00 	mov    DWORD PTR [esp+0x4],0x8
  84:	00 
  85:	8d 85 2c ff ff ff    	lea    eax,[ebp-0xd4]
  8b:	89 04 24             	mov    DWORD PTR [esp],eax
  8e:	c7 85 f8 fe ff ff 01 	mov    DWORD PTR [ebp-0x108],0x1
  95:	00 00 00 
  98:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
  9e:	e8 00 00 00 00       	call   a3 <_main+0xa3>
  a3:	83 ec 08             	sub    esp,0x8
  a6:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
  ac:	e8 00 00 00 00       	call   b1 <_main+0xb1>
  b1:	c7 85 34 ff ff ff 00 	mov    DWORD PTR [ebp-0xcc],0x0
  b8:	00 00 00 
  bb:	c7 85 38 ff ff ff 00 	mov    DWORD PTR [ebp-0xc8],0x0
  c2:	00 00 00 
  c5:	c7 85 3c ff ff ff 00 	mov    DWORD PTR [ebp-0xc4],0x0
  cc:	00 00 00 
  cf:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
  d6:	ff ff ff 
  d9:	c7 85 f0 fe ff ff 00 	mov    DWORD PTR [ebp-0x110],0x0
  e0:	00 00 00 
  e3:	90                   	nop
  e4:	8d 85 30 ff ff ff    	lea    eax,[ebp-0xd0]
  ea:	89 04 24             	mov    DWORD PTR [esp],eax
  ed:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
  f4:	00 00 00 
  f7:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
  fd:	e8 00 00 00 00       	call   102 <_main+0x102>
 102:	51                   	push   ecx
 103:	8b 10                	mov    edx,DWORD PTR [eax]
 105:	8b 52 f4             	mov    edx,DWORD PTR [edx-0xc]
 108:	f6 44 10 14 05       	test   BYTE PTR [eax+edx*1+0x14],0x5
 10d:	74 5d                	je     16c <_main+0x16c>
 10f:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 115:	89 14 24             	mov    DWORD PTR [esp],edx
 118:	b9 00 00 00 00       	mov    ecx,0x0
 11d:	e8 00 00 00 00       	call   122 <_main+0x122>
 122:	52                   	push   edx
 123:	89 04 24             	mov    DWORD PTR [esp],eax
 126:	e8 00 00 00 00       	call   12b <_main+0x12b>
 12b:	8b 85 34 ff ff ff    	mov    eax,DWORD PTR [ebp-0xcc]
 131:	85 c0                	test   eax,eax
 133:	74 08                	je     13d <_main+0x13d>
 135:	89 04 24             	mov    DWORD PTR [esp],eax
 138:	e8 00 00 00 00       	call   13d <_main+0x13d>
 13d:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 144:	ff ff ff 
 147:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
 14d:	e8 00 00 00 00       	call   152 <_main+0x152>
 152:	8d 95 f4 fe ff ff    	lea    edx,[ebp-0x10c]
 158:	89 14 24             	mov    DWORD PTR [esp],edx
 15b:	e8 00 00 00 00       	call   160 <_main+0x160>
 160:	31 c0                	xor    eax,eax
 162:	8b 4d fc             	mov    ecx,DWORD PTR [ebp-0x4]
 165:	c9                   	leave  
 166:	8d 61 fc             	lea    esp,[ecx-0x4]
 169:	c3                   	ret    
 16a:	66 90                	xchg   ax,ax
 16c:	8b 85 30 ff ff ff    	mov    eax,DWORD PTR [ebp-0xd0]
 172:	39 85 ec fe ff ff    	cmp    DWORD PTR [ebp-0x114],eax
 178:	75 0e                	jne    188 <_main+0x188>
 17a:	ff 85 f0 fe ff ff    	inc    DWORD PTR [ebp-0x110]
 180:	e9 5f ff ff ff       	jmp    e4 <_main+0xe4>
 185:	8d 76 00             	lea    esi,[esi+0x0]
 188:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
 18c:	8d 95 34 ff ff ff    	lea    edx,[ebp-0xcc]
 192:	89 14 24             	mov    DWORD PTR [esp],edx
 195:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
 19c:	00 00 00 
 19f:	e8 2c 00 00 00       	call   1d0 <_main+0x1d0>
 1a4:	84 c0                	test   al,al
 1a6:	74 3c                	je     1e4 <_main+0x1e4>
 1a8:	8b 85 30 ff ff ff    	mov    eax,DWORD PTR [ebp-0xd0]
 1ae:	89 44 24 04          	mov    DWORD PTR [esp+0x4],eax
 1b2:	8d 85 34 ff ff ff    	lea    eax,[ebp-0xcc]
 1b8:	89 04 24             	mov    DWORD PTR [esp],eax
 1bb:	e8 7c 00 00 00       	call   23c <_main+0x23c>
 1c0:	8b 95 30 ff ff ff    	mov    edx,DWORD PTR [ebp-0xd0]
 1c6:	89 95 ec fe ff ff    	mov    DWORD PTR [ebp-0x114],edx
 1cc:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 1d2:	8d 54 02 01          	lea    edx,[edx+eax*1+0x1]
 1d6:	89 95 f0 fe ff ff    	mov    DWORD PTR [ebp-0x110],edx
 1dc:	e9 03 ff ff ff       	jmp    e4 <_main+0xe4>
 1e1:	8d 76 00             	lea    esi,[esi+0x0]
 1e4:	8b 85 38 ff ff ff    	mov    eax,DWORD PTR [ebp-0xc8]
 1ea:	3b 85 3c ff ff ff    	cmp    eax,DWORD PTR [ebp-0xc4]
 1f0:	74 26                	je     218 <_main+0x218>
 1f2:	85 c0                	test   eax,eax
 1f4:	74 08                	je     1fe <_main+0x1fe>
 1f6:	8b 95 30 ff ff ff    	mov    edx,DWORD PTR [ebp-0xd0]
 1fc:	89 10                	mov    DWORD PTR [eax],edx
 1fe:	83 c0 04             	add    eax,0x4
 201:	89 85 38 ff ff ff    	mov    DWORD PTR [ebp-0xc8],eax
 207:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
 20e:	ff ff ff 
 211:	e9 ce fe ff ff       	jmp    e4 <_main+0xe4>
 216:	66 90                	xchg   ax,ax
 218:	8d 95 30 ff ff ff    	lea    edx,[ebp-0xd0]
 21e:	89 54 24 04          	mov    DWORD PTR [esp+0x4],edx
 222:	89 04 24             	mov    DWORD PTR [esp],eax
 225:	c7 85 f8 fe ff ff 02 	mov    DWORD PTR [ebp-0x108],0x2
 22c:	00 00 00 
 22f:	8d 8d 34 ff ff ff    	lea    ecx,[ebp-0xcc]
 235:	e8 00 00 00 00       	call   23a <_main+0x23a>
 23a:	83 ec 08             	sub    esp,0x8
 23d:	c7 85 ec fe ff ff ff 	mov    DWORD PTR [ebp-0x114],0xffffffff
 244:	ff ff ff 
 247:	e9 98 fe ff ff       	jmp    e4 <_main+0xe4>
 24c:	83 c5 08             	add    ebp,0x8
 24f:	8b 85 fc fe ff ff    	mov    eax,DWORD PTR [ebp-0x104]
 255:	89 85 f0 fe ff ff    	mov    DWORD PTR [ebp-0x110],eax
 25b:	8b 85 f8 fe ff ff    	mov    eax,DWORD PTR [ebp-0x108]
 261:	85 c0                	test   eax,eax
 263:	74 05                	je     26a <_main+0x26a>
 265:	48                   	dec    eax
 266:	74 25                	je     28d <_main+0x28d>
 268:	0f 0b                	ud2    
 26a:	8d 8d 2c ff ff ff    	lea    ecx,[ebp-0xd4]
 270:	e8 00 00 00 00       	call   275 <_main+0x275>
 275:	8b 95 f0 fe ff ff    	mov    edx,DWORD PTR [ebp-0x110]
 27b:	89 14 24             	mov    DWORD PTR [esp],edx
 27e:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 285:	ff ff ff 
 288:	e8 00 00 00 00       	call   28d <_main+0x28d>
 28d:	8b 85 34 ff ff ff    	mov    eax,DWORD PTR [ebp-0xcc]
 293:	85 c0                	test   eax,eax
 295:	74 08                	je     29f <_main+0x29f>
 297:	89 04 24             	mov    DWORD PTR [esp],eax
 29a:	e8 00 00 00 00       	call   29f <_main+0x29f>
 29f:	c7 85 f8 fe ff ff 00 	mov    DWORD PTR [ebp-0x108],0x0
 2a6:	00 00 00 
 2a9:	8d 8d 40 ff ff ff    	lea    ecx,[ebp-0xc0]
 2af:	e8 00 00 00 00       	call   2b4 <_main+0x2b4>
 2b4:	8b 85 f0 fe ff ff    	mov    eax,DWORD PTR [ebp-0x110]
 2ba:	89 04 24             	mov    DWORD PTR [esp],eax
 2bd:	c7 85 f8 fe ff ff ff 	mov    DWORD PTR [ebp-0x108],0xffffffff
 2c4:	ff ff ff 
 2c7:	e8 00 00 00 00       	call   2cc <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi>

000002cc <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi>:
 2cc:	83 ec 1c             	sub    esp,0x1c
 2cf:	b9 08 00 00 00       	mov    ecx,0x8
 2d4:	e8 00 00 00 00       	call   2d9 <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi+0xd>
 2d9:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 2e0:	e8 00 00 00 00       	call   2e5 <__GLOBAL__sub_I__Z10match_backRSt6vectorIiSaIiEEi+0x19>
 2e5:	83 c4 1c             	add    esp,0x1c
 2e8:	c3                   	ret    
 2e9:	90                   	nop
 2ea:	90                   	nop
 2eb:	90                   	nop

Sie

Код: pascal

000000ec <__Z7deflateii>:
  ec:	56                   	push   esi
  ed:	53                   	push   ebx
  ee:	83 ec 14             	sub    esp,0x14
  f1:	8b 5c 24 20          	mov    ebx,DWORD PTR [esp+0x20]
  f5:	8b 74 24 24          	mov    esi,DWORD PTR [esp+0x24]
  f9:	8d 76 00             	lea    esi,[esi+0x0]
  fc:	c7 44 24 08 01 00 00 	mov    DWORD PTR [esp+0x8],0x1
 103:	00 
 104:	c7 44 24 04 00 00 00 	mov    DWORD PTR [esp+0x4],0x0
 10b:	00 
 10c:	c7 04 24 00 00 00 00 	mov    DWORD PTR [esp],0x0
 113:	e8 00 00 00 00       	call   118 <__Z7deflateii+0x2c>
 118:	85 db                	test   ebx,ebx
 11a:	7e 64                	jle    180 <__Z7deflateii+0x94>
 11c:	8d 4b ff             	lea    ecx,[ebx-0x1]
 11f:	8b 04 8d 00 00 00 00 	mov    eax,DWORD PTR [ecx*4+0x0]
 126:	3b 04 9d 00 00 00 00 	cmp    eax,DWORD PTR [ebx*4+0x0]
 12d:	74 35                	je     164 <__Z7deflateii+0x78>
 12f:	bb 01 00 00 00       	mov    ebx,0x1
 134:	89 f0                	mov    eax,esi
 136:	83 f8 0b             	cmp    eax,0xb
 139:	77 11                	ja     14c <__Z7deflateii+0x60>
 13b:	40                   	inc    eax
 13c:	8b 14 b5 00 00 00 00 	mov    edx,DWORD PTR [esi*4+0x0]
 143:	39 14 85 00 00 00 00 	cmp    DWORD PTR [eax*4+0x0],edx
 14a:	74 ea                	je     136 <__Z7deflateii+0x4a>
 14c:	8d 14 03             	lea    edx,[ebx+eax*1]
 14f:	29 f2                	sub    edx,esi
 151:	83 fa 02             	cmp    edx,0x2
 154:	7e 22                	jle    178 <__Z7deflateii+0x8c>
 156:	01 15 04 00 00 00    	add    DWORD PTR ds:0x4,edx
 15c:	89 cb                	mov    ebx,ecx
 15e:	89 c6                	mov    esi,eax
 160:	eb 9a                	jmp    fc <__Z7deflateii+0x10>
 162:	66 90                	xchg   ax,ax
 164:	85 c9                	test   ecx,ecx
 166:	74 cc                	je     134 <__Z7deflateii+0x48>
 168:	49                   	dec    ecx
 169:	39 04 8d 00 00 00 00 	cmp    DWORD PTR [ecx*4+0x0],eax
 170:	74 f2                	je     164 <__Z7deflateii+0x78>
 172:	29 cb                	sub    ebx,ecx
 174:	eb be                	jmp    134 <__Z7deflateii+0x48>
 176:	66 90                	xchg   ax,ax
 178:	83 c4 14             	add    esp,0x14
 17b:	5b                   	pop    ebx
 17c:	5e                   	pop    esi
 17d:	c3                   	ret    
 17e:	66 90                	xchg   ax,ax
 180:	89 d9                	mov    ecx,ebx
 182:	31 db                	xor    ebx,ebx
 184:	eb ae                	jmp    134 <__Z7deflateii+0x48>
 186:	66 90                	xchg   ax,ax

00000188 <__Z5main2v>:
 188:	56                   	push   esi
 189:	53                   	push   ebx
 18a:	83 ec 14             	sub    esp,0x14
 18d:	31 c0                	xor    eax,eax
 18f:	83 f8 0a             	cmp    eax,0xa
 192:	77 1a                	ja     1ae <__Z5main2v+0x26>
 194:	8d 50 01             	lea    edx,[eax+0x1]
 197:	8b 0c 95 00 00 00 00 	mov    ecx,DWORD PTR [edx*4+0x0]
 19e:	39 0c 85 00 00 00 00 	cmp    DWORD PTR [eax*4+0x0],ecx
 1a5:	74 51                	je     1f8 <__Z5main2v+0x70>
 1a7:	89 d0                	mov    eax,edx
 1a9:	83 f8 0a             	cmp    eax,0xa
 1ac:	76 e6                	jbe    194 <__Z5main2v+0xc>
 1ae:	a1 04 00 00 00       	mov    eax,ds:0x4
 1b3:	89 04 24             	mov    DWORD PTR [esp],eax
 1b6:	b9 00 00 00 00       	mov    ecx,0x0
 1bb:	e8 00 00 00 00       	call   1c0 <__Z5main2v+0x38>
 1c0:	53                   	push   ebx
 1c1:	89 c6                	mov    esi,eax
 1c3:	8b 00                	mov    eax,DWORD PTR [eax]
 1c5:	8b 40 f4             	mov    eax,DWORD PTR [eax-0xc]
 1c8:	8b 5c 06 7c          	mov    ebx,DWORD PTR [esi+eax*1+0x7c]
 1cc:	85 db                	test   ebx,ebx
 1ce:	74 50                	je     220 <__Z5main2v+0x98>
 1d0:	80 7b 1c 00          	cmp    BYTE PTR [ebx+0x1c],0x0
 1d4:	74 32                	je     208 <__Z5main2v+0x80>
 1d6:	8a 43 27             	mov    al,BYTE PTR [ebx+0x27]
 1d9:	0f be c0             	movsx  eax,al
 1dc:	89 04 24             	mov    DWORD PTR [esp],eax
 1df:	89 f1                	mov    ecx,esi
 1e1:	e8 00 00 00 00       	call   1e6 <__Z5main2v+0x5e>
 1e6:	52                   	push   edx
 1e7:	89 c1                	mov    ecx,eax
 1e9:	e8 00 00 00 00       	call   1ee <__Z5main2v+0x66>
 1ee:	31 c0                	xor    eax,eax
 1f0:	83 c4 14             	add    esp,0x14
 1f3:	5b                   	pop    ebx
 1f4:	5e                   	pop    esi
 1f5:	c3                   	ret    
 1f6:	66 90                	xchg   ax,ax
 1f8:	89 54 24 04          	mov    DWORD PTR [esp+0x4],edx
 1fc:	89 04 24             	mov    DWORD PTR [esp],eax
 1ff:	e8 e8 fe ff ff       	call   ec <__Z7deflateii>
 204:	eb 89                	jmp    18f <__Z5main2v+0x7>
 206:	66 90                	xchg   ax,ax
 208:	89 d9                	mov    ecx,ebx
 20a:	e8 00 00 00 00       	call   20f <__Z5main2v+0x87>
 20f:	8b 03                	mov    eax,DWORD PTR [ebx]
 211:	c7 04 24 0a 00 00 00 	mov    DWORD PTR [esp],0xa
 218:	89 d9                	mov    ecx,ebx
 21a:	ff 50 18             	call   DWORD PTR [eax+0x18]
 21d:	51                   	push   ecx
 21e:	eb b9                	jmp    1d9 <__Z5main2v+0x51>
 220:	e8 00 00 00 00       	call   225 <__Z5main2v+0x9d>
 225:	90                   	nop
 226:	90                   	nop
 227:	90                   	nop

...

Рейтинг:

0 / 0

18.03.2016, 19:48

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39195782

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

mingw 4.7.1
mingw32-g++.exe -Wall -fexceptions -fomit-frame-pointer -O2

...

Рейтинг:

0 / 0

18.03.2016, 20:02

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39195879

Anatoly Moskovsky

Участник

Откуда: Odessa

Сообщения: 6 713

Рейтинг: 0 / 0

SiemarglЧуть позже выложу ассемблер
Для начала неплохо было бы исходник хотя бы выложить )))

...

Рейтинг:

0 / 0

19.03.2016, 01:30

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39195939

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Anatoly MoskovskySiemarglЧуть позже выложу ассемблер
Для начала неплохо было бы исходник хотя бы выложить )))
Да хотелось подавану дать время самому подумать. Думаешь уже хватит?

...

Рейтинг:

0 / 0

19.03.2016, 10:21

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196227

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Anatoly MoskovskySiemarglЧуть позже выложу ассемблер
Для начала неплохо было бы исходник хотя бы выложить )))

Код: plaintext

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.

int erased;
int is[] = {10, 3,3, 2, 2, 1, 1, 1, 2, 2, 3, 3};
int trick;

int deflate(int left, int right)
{
    TRC;
    int new_left = left, new_right = right;
    while(new_left > 0 && is[--new_left] == is[left]);

    while(new_right < sizeof is / sizeof(is[0]) && is[++new_right] == is[right]);

    int erased_in = left - new_left + new_right - right;
    if(erased_in > 2)
    {
        erased += erased_in;
        new_right = deflate(new_left, new_right);
    }

    return new_right;
}

int main()
{

    for (int i =0; i < sizeof is / sizeof(is[0]) -1;)
        if(is[i] == is[i+1])
            i = deflate(i, i+1);
        else
            i++;

    std::cout << erased << std::endl;
    return 0;
}

Dima TSiemarglПриврал. Проверил. Вдвое.
На данных 10 3 3 2 2 1 1 1 2 2 3 3
у АМ 13 вызовов функций (не включая работу с вектором)
у меня - 6
у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13.
Я не верю =)

ИМХО, у них от шаблонного объектного кода крыша съезжает. В простых случаях - нормально инлайнит и оптимизирует, но с сегодняшней модой на простые пятимерные шаблоны смотри сам, какой код генерится. Это типовой образец причем.

...

Рейтинг:

0 / 0

19.03.2016, 22:14

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196315

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

SiemarglDima Tпропущено...

у АМ 0 (ноль) вызовов функций. Вызовы компилятор уберет. Если не веришь компиляторам - у него можно просто скопипастить весь код в main(), функции там только для для читаемости кода, с рекурсией это невозможно, так что 6:0, а не 6:13.
Я не верю =)

ИМХО, у них от шаблонного объектного кода крыша съезжает. В простых случаях - нормально инлайнит и оптимизирует, но с сегодняшней модой на простые пятимерные шаблоны смотри сам, какой код генерится. Это типовой образец причем.
ИМХУ не туда смотришь. При чем тут шаблоны? Замени vector<> на массив + немного кода и не будет шаблонов. vector<> тормознее обычного массива, не спорю. Но при необходимости его можно заменить на обычный массив.

У меня так скомпилировалось MS VC 2015

Код: plaintext

bool match_back(std::vector<int>& state, int v)
{
	return state.size() >= 2
		&& state[state.size() - 1] == v
		&& state[state.size() - 2] == v;
}

int erase_back(std::vector<int>& state, int v)
{
	int erased = 0;
	while (state.size() > 0 && state[state.size() - 1] == v) {
		state.pop_back();
		erased++;
	}
	return erased;
}


int main()
{
00C42240  push        ebp  
00C42241  mov         ebp,esp  
00C42243  push        0FFFFFFFFh  
00C42245  push        0C6902Dh  
00C4224A  mov         eax,dword ptr fs:[00000000h]  
00C42250  push        eax  
00C42251  sub         esp,0D0h  
00C42257  mov         eax,dword ptr [__security_cookie (0C761BCh)]  
00C4225C  xor         eax,ebp  
00C4225E  mov         dword ptr [ebp-10h],eax  
00C42261  push        ebx  
00C42262  push        esi  
00C42263  push        edi  
00C42264  push        eax  
00C42265  lea         eax,[ebp-0Ch]  
00C42268  mov         dword ptr fs:[00000000h],eax  
00C4226E  push        0A8h  
00C42273  lea         eax,[is]  
00C42279  push        0  
00C4227B  push        eax  
00C4227C  call        memset (0C51E10h)  
00C42281  add         esp,0Ch  
	//std::istringstream is ("5 1 3 3 3 2");
	std::istringstream is("10 3 3 2 1 1 1 2 2 3 3");
00C42284  mov         dword ptr [ebp-18h],0Fh  
00C4228B  lea         ecx,[ebp-2Ch]  
00C4228E  mov         dword ptr [ebp-1Ch],0  
00C42295  mov         byte ptr [ebp-2Ch],0  
00C42299  push        16h  
00C4229B  push        offset string "10 3 3 2 1 1 1 2 2 3 3" (0C72888h)  
00C422A0  call        std::basic_string<char,std::char_traits<char>,std::allocator<char> >::assign (0C45000h)  
00C422A5  sub         esp,8  
00C422A8  mov         dword ptr [ebp-4],0  
00C422AF  lea         eax,[ebp-2Ch]  
00C422B2  lea         ecx,[is]  
00C422B8  push        eax  
00C422B9  call        std::basic_istringstream<char,std::char_traits<char>,std::allocator<char> >::basic_istringstream<char,std::char_traits<char>,std::allocator<char> > (0C42740h)  
00C422BE  mov         eax,dword ptr [ebp-18h]  
00C422C1  cmp         eax,10h  
00C422C4  jb          main+93h (0C422D3h)  
00C422C6  inc         eax  
00C422C7  lea         ecx,[ebp-2Ch]  
00C422CA  push        eax  
00C422CB  push        dword ptr [ebp-2Ch]  
00C422CE  call        std::allocator<char>::deallocate (0C455F0h)  
00C422D3  xorps       xmm0,xmm0  
	std::vector<int> state;
00C422D6  xor         ebx,ebx  
	int erased = 0;
00C422D8  xor         edi,edi  
00C422DA  movq        mmword ptr [ebp-20h],xmm0  
	std::vector<int> state;
00C422DF  xor         esi,esi  
	int erased = 0;
00C422E1  mov         dword ptr [ebp-0D8h],edi  
00C422E7  mov         dword ptr [state],ebx  
00C422EA  mov         dword ptr [ebp-1Ch],esi  
00C422ED  mov         dword ptr [ebp-18h],ebx  
	int erase_v = -1;
	int v;
	while (is >> v) {
00C422F0  lea         eax,[v]  
00C422F3  mov         byte ptr [ebp-4],3  
00C422F7  push        eax  
00C422F8  lea         ecx,[is]  
00C422FE  mov         dword ptr [ebp-0DCh],0FFFFFFFFh  
00C42308  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C4230D  mov         ecx,dword ptr [eax]  
00C4230F  mov         ecx,dword ptr [ecx+4]  
00C42312  test        byte ptr [ecx+eax+0Ch],6  
00C42317  jne         main+181h (0C423C1h)  
00C4231D  nop         dword ptr [eax]  
		if (erase_v == v) {
00C42320  mov         edx,dword ptr [v]  
00C42323  cmp         dword ptr [erase_v],edx  
00C42329  jne         main+0F4h (0C42334h)  
			erased++;
00C4232B  inc         edi  
00C4232C  mov         dword ptr [erased],edi  
00C42332  jmp         main+162h (0C423A2h)  
		}
		else if (match_back(state, v)) {
00C42334  mov         ecx,esi  
00C42336  sub         ecx,ebx  
00C42338  mov         eax,ecx  
00C4233A  sar         eax,2  
00C4233D  cmp         eax,2  
00C42340  jb          main+146h (0C42386h)  
00C42342  cmp         dword ptr [ebx+eax*4-4],edx  
00C42346  jne         main+146h (0C42386h)  
00C42348  cmp         dword ptr [ebx+eax*4-8],edx  
00C4234C  jne         main+146h (0C42386h)  
			erased += erase_back(state, v);
00C4234E  xor         edi,edi  
00C42350  test        eax,eax  
00C42352  je          main+12Dh (0C4236Dh)  
00C42354  cmp         dword ptr [ebx+eax*4-4],edx  
00C42358  jne         main+12Ah (0C4236Ah)  
00C4235A  sub         ecx,4  
00C4235D  sub         esi,4  
00C42360  mov         eax,ecx  
00C42362  inc         edi  
00C42363  sar         eax,2  
00C42366  test        eax,eax  
00C42368  jne         main+114h (0C42354h)  
00C4236A  mov         dword ptr [ebp-1Ch],esi  
			erase_v = v;
			erased++;
00C4236D  mov         eax,dword ptr [erased]  
00C42373  inc         eax  
00C42374  mov         dword ptr [erase_v],edx  
00C4237A  add         eax,edi  
00C4237C  mov         dword ptr [erased],eax  
		}
		else {
00C42382  mov         edi,eax  
00C42384  jmp         main+162h (0C423A2h)  
			erase_v = -1;
			state.push_back(v);
00C42386  lea         eax,[v]  
00C42389  mov         dword ptr [erase_v],0FFFFFFFFh  
00C42393  push        eax  
00C42394  lea         ecx,[state]  
00C42397  call        std::vector<int,std::allocator<int> >::push_back (0C42480h)  
00C4239C  mov         esi,dword ptr [ebp-1Ch]  
00C4239F  mov         ebx,dword ptr [state]  
	int erase_v = -1;
	int v;
	while (is >> v) {
00C423A2  lea         eax,[v]  
00C423A5  push        eax  
00C423A6  lea         ecx,[is]  
00C423AC  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C423B1  mov         ecx,dword ptr [eax]  
00C423B3  mov         ecx,dword ptr [ecx+4]  
00C423B6  test        byte ptr [ecx+eax+0Ch],6  
00C423BB  je          main+0E0h (0C42320h)  
		}
	}
	cout << erased << endl;
00C423C1  push        edi  
00C423C2  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0C42DE0h)  
00C423C7  push        eax  
00C423C8  call        std::endl<char,std::char_traits<char> > (0C48CB0h)  
00C423CD  add         esp,4  
	return 0;

Как видишь match_back() и erase_back() заинлайнились.

...

Рейтинг:

0 / 0

20.03.2016, 08:58

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196321

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Вот так твой код скомпилировался

Код: plaintext

int erased;
int is[] = { 10, 3,3, 2, 2, 1, 1, 1, 2, 2, 3, 3 };
int trick;

int deflate(int left, int right)
{
00832130  push        esi  
00832131  push        edi  
00832132  mov         edi,ecx  
	//TRC;
	int new_left = left, new_right = right;
00832134  mov         eax,edx  
00832136  mov         esi,edi  
	while (new_left > 0 && is[--new_left] == is[left]);
00832138  test        esi,esi  
0083213A  jle         deflate+20h (0832150h)  
0083213C  mov         ecx,dword ptr [esi*4+85A858h]  
00832143  dec         esi  
00832144  cmp         ecx,dword ptr is (085A85Ch)[edi*4]  
0083214B  je          deflate+8h (0832138h)  
0083214D  nop         dword ptr [eax]  

	while (new_right < sizeof is / sizeof(is[0]) && is[++new_right] == is[right]);
00832150  cmp         eax,0Ch  
00832153  jae         deflate+36h (0832166h)  
00832155  mov         ecx,dword ptr [eax*4+85A860h]  
0083215C  inc         eax  
0083215D  cmp         ecx,dword ptr is (085A85Ch)[edx*4]  
00832164  je          deflate+20h (0832150h)  

	int erased_in = left - new_left + new_right - right;
00832166  mov         ecx,eax  
00832168  sub         ecx,esi  
0083216A  sub         ecx,edx  
0083216C  add         ecx,edi  
0083216E  pop         edi  
	if (erased_in > 2)
0083216F  cmp         ecx,2  
00832172  jle         deflate+54h (0832184h)  
	{
		erased += erased_in;
00832174  add         dword ptr [erased (085FE94h)],ecx  
		new_right = deflate(new_left, new_right);
0083217A  mov         edx,eax  
0083217C  mov         ecx,esi  
0083217E  pop         esi  
0083217F  jmp         deflate (0832130h)  
00832184  pop         esi  
	}

	return new_right;
}
00832185  ret  
--- No source file -------------------------------------------------------------
00832186  int         3  
00832187  int         3  
00832188  int         3  
00832189  int         3  
0083218A  int         3  
0083218B  int         3  
0083218C  int         3  
0083218D  int         3  
0083218E  int         3  
0083218F  int         3  
--- m:\vc2015\test\test.cpp ----------------------------------------------------

int main()
{
00832190  push        esi  

	for (int i = 0; i < sizeof is / sizeof(is[0]) - 1;)
00832191  xor         edx,edx  
00832193  push        edi  
00832194  nop         dword ptr [eax]  
00832198  nop         dword ptr [eax+eax]  
		if (is[i] == is[i + 1])
008321A0  mov         ecx,dword ptr is (085A85Ch)[edx*4]  
008321A7  cmp         ecx,dword ptr [edx*4+85A860h]  
008321AE  jne         main+6Bh (08321FBh)  
			i = deflate(i, i + 1);
008321B0  lea         edi,[edx+1]  
008321B3  mov         esi,edx  
008321B5  mov         eax,edi  
008321B7  test        esi,esi  
008321B9  jle         main+35h (08321C5h)  
008321BB  dec         esi  
008321BC  cmp         dword ptr is (085A85Ch)[esi*4],ecx  
008321C3  je          main+27h (08321B7h)  
008321C5  cmp         eax,0Ch  
008321C8  jae         main+4Bh (08321DBh)  
008321CA  mov         ecx,dword ptr [eax*4+85A860h]  
008321D1  inc         eax  
008321D2  cmp         ecx,dword ptr is (085A85Ch)[edi*4]  
008321D9  je          main+35h (08321C5h)  
			i = deflate(i, i + 1);
008321DB  mov         ecx,eax  
008321DD  sub         ecx,esi  
008321DF  sub         ecx,edi  
008321E1  add         ecx,edx  
008321E3  cmp         ecx,2  
008321E6  jle         main+67h (08321F7h)  
008321E8  add         dword ptr [erased (085FE94h)],ecx  
008321EE  mov         edx,eax  
008321F0  mov         ecx,esi  
008321F2  call        deflate (0832130h)  
008321F7  mov         edx,eax  
		else
008321F9  jmp         main+6Ch (08321FCh)  
			i++;
008321FB  inc         edx  

	for (int i = 0; i < sizeof is / sizeof(is[0]) - 1;)
008321FC  cmp         edx,0Bh  
008321FF  jb          main+10h (08321A0h)  

	std::cout << erased << std::endl;
00832201  push        ecx  
00832202  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0832300h)  
00832207  push        eax  
00832208  call        std::endl<char,std::char_traits<char> > (0834790h)  
0083220D  add         esp,4  
	return 0;

deflate() не инлайнится, т.к. рекурсия.

...

Рейтинг:

0 / 0

20.03.2016, 09:06

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196365

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima T,

Рекурсия, какая рекурсия?

Где ты видишь рекурсивный вызов в ассемблере? =)

...

Рейтинг:

0 / 0

20.03.2016, 11:30

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196367

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

тут

Код: plaintext

1.
2.
3.
4.
5.

int deflate(int left, int right)
{
...
new_right = deflate(new_left, new_right);
...

...

Рейтинг:

0 / 0

20.03.2016, 11:36

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196425

Anatoly Moskovsky

Участник

Откуда: Odessa

Сообщения: 6 713

Рейтинг: 0 / 0

Господа, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? )))

...

Рейтинг:

0 / 0

20.03.2016, 14:27

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196439

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Anatoly MoskovskyГоспода, вам не стыдно сравнивать скорость кода который читает из потока и кода который работает с уже считанным массивом? )))
Это не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать.

Мы же не секундомером мерим, а количество операций обсуждаем.

PS Еще код Siemargl 18954238 неправильно считает. В принципе это тоже не важно :)

Код: plaintext

int is[] = { 10, 3, 3, 2, 2, 1, 1, 1, 3, 2, 3, 3 };

...

Рейтинг:

0 / 0

20.03.2016, 14:54

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196451

Anatoly Moskovsky

Участник

Откуда: Odessa

Сообщения: 6 713

Рейтинг: 0 / 0

Dima TЭто не принципиально. Оба кода в итоге прочитают массив целиком. Хотя можно было бы и не дочитывать.
Это принципиально. Потому что чтение например 1000 чисел займет несколько миллисекунд, а сам алгоритм их обработки - несколько микросекунд (что один что второй). Поэтому считать такты на вызовы функций, когда I/O на порядки медленнее - бессмысленная работа ))

...

Рейтинг:

0 / 0

20.03.2016, 15:18

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196508

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima T,

Срочный сервис пак =)

Код: plaintext

1.
2.

        if (is[new_left] == is[new_right])
            new_right = deflate(new_left, new_right);

С точки зрения практической выгоды, конечно дисковое чтение гораздо дольше.

Но это пример, когда рекурсивный алгоритм короче и эффективнее. Причем оба компилятора оптимизировали хвостовую рекурсию.

Чтение из потока дает небольшую добавку в инструкциях (хотя хз, почему MSVC дважды сгенерил этот кусок)

Код: plaintext

1.
2.
3.
4.
5.
6.
7.
8.
9.

00C422F0  lea         eax,[v]  
00C422F3  mov         byte ptr [ebp-4],3  
00C422F7  push        eax  
00C422F8  lea         ecx,[is]  
00C422FE  mov         dword ptr [ebp-0DCh],0FFFFFFFFh  
00C42308  call        std::basic_istream<char,std::char_traits<char> >::operator>> (0C42FB0h)  
00C4230D  mov         ecx,dword ptr [eax]  
00C4230F  mov         ecx,dword ptr [ecx+4]  
00C42312  test        byte ptr [ecx+eax+0Ch],6

...

Рейтинг:

0 / 0

20.03.2016, 16:47

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196516

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Хотя нет, GCC рекурсию оставил.

...

Рейтинг:

0 / 0

20.03.2016, 17:04

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196523

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Написал для сравнения с учетом вышеизложенных замечаний. (без функций, шаблонов и потокового чтения)

Исходник

Код: plaintext

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.

int is[] = { 10, 3, 3, 2, 2, 1, 1, 1, 2, 3, 3 };

int main()
{
	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
	int cnt = 1;
	for (; cur < end; cur++) {
		if(*(cur - 1) == *cur) {
			cnt++;
		} else if(cnt >= 3) {
			break;
		} else {
			cnt = 1;
		}
	}
	if(cnt >= 3) {
		// Схлапывание по краям найденного
		while(1) {
			int* left = cur - cnt - 1;
			if (*left != *cur) break;
			int cnt_add = 2;
			// Подсчет влево
			left--;
			if (left >= is && *left == *cur) cnt_add++;
			// Подсчет вправо
			cur++;
			if(cur < end && *(cur - 1) == *cur) cnt_add++;
			if (cnt_add < 3) break;
			cnt += cnt_add;
		}
	}

	std::cout << cnt << std::endl;
	return 0;
}

в асме

Код: plaintext

	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
00DC2130  mov         eax,0DEEB54h  
	int cnt = 1;
00DC2135  mov         edx,1  
00DC213A  nop         word ptr [eax+eax]  
		if(*(cur - 1) == *cur) {
00DC2140  mov         ecx,dword ptr [eax-4]  
00DC2143  cmp         ecx,dword ptr [eax]  
00DC2145  jne         main+1Ah (0DC214Ah)  
			cnt++;
00DC2147  inc         edx  
00DC2148  jmp         main+24h (0DC2154h)  
		} else if(cnt >= 3) {
00DC214A  cmp         edx,3  
00DC214D  jge         main+33h (0DC2163h)  
			break;
		} else {
			cnt = 1;
00DC214F  mov         edx,1  
	for (; cur < end; cur++) {
00DC2154  add         eax,4  
00DC2157  cmp         eax,0DEEB7Ch  
00DC215C  jb          main+10h (0DC2140h)  
		}
	}
	if(cnt >= 3) {
00DC215E  cmp         edx,3  
00DC2161  jl          main+91h (0DC21C1h)  
00DC2163  push        edi  
		// Схлапывание по краям найденного
		while(1) {
			int* left = cur - cnt - 1;
00DC2164  lea         ecx,[edx*4+4]  
00DC216B  mov         edi,eax  
00DC216D  sub         edi,ecx  
			if (*left != *cur) break;
00DC216F  mov         ecx,dword ptr [eax]  
00DC2171  cmp         dword ptr [edi],ecx  
00DC2173  jne         main+90h (0DC21C0h)  
00DC2175  push        ebx  
00DC2176  mov         ebx,3  
00DC217B  push        esi  
00DC217C  nop         dword ptr [eax]  
			int cnt_add = 2;
			// Подсчет влево
			left--;
00DC2180  sub         edi,4  
00DC2183  mov         esi,2  
			if (left >= is && *left == *cur) cnt_add++;
00DC2188  cmp         edi,offset is (0DEEB50h)  
00DC218E  jb          main+65h (0DC2195h)  
00DC2190  cmp         dword ptr [edi],ecx  
00DC2192  cmove       esi,ebx  
			// Подсчет вправо
			cur++;
00DC2195  add         eax,4  
			if(cur < end && *(cur - 1) == *cur) cnt_add++;
00DC2198  cmp         eax,0DEEB7Ch  
00DC219D  jae         main+77h (0DC21A7h)  
00DC219F  mov         ecx,dword ptr [eax-4]  
00DC21A2  cmp         ecx,dword ptr [eax]  
00DC21A4  jne         main+77h (0DC21A7h)  
00DC21A6  inc         esi  
			if (cnt_add < 3) break;
00DC21A7  cmp         esi,ebx  
00DC21A9  jl          main+8Eh (0DC21BEh)  
			cnt += cnt_add;
00DC21AB  add         edx,esi  
00DC21AD  mov         edi,eax  
00DC21AF  lea         ecx,[edx*4+4]  
00DC21B6  sub         edi,ecx  
			cnt += cnt_add;
00DC21B8  mov         ecx,dword ptr [eax]  
00DC21BA  cmp         dword ptr [edi],ecx  
00DC21BC  je          main+50h (0DC2180h)  
00DC21BE  pop         esi  
00DC21BF  pop         ebx  
00DC21C0  pop         edi  
		}
	}

	std::cout << cnt << std::endl;
00DC21C1  push        edx  
00DC21C2  call        std::basic_ostream<char,std::char_traits<char> >::operator<< (0DC22C0h)  
00DC21C7  push        eax  
00DC21C8  call        std::endl<char,std::char_traits<char> > (0DC4750h)  
00DC21CD  add         esp,4  
	return 0;

...

Рейтинг:

0 / 0

20.03.2016, 17:32

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196552

Dima T

Участник

Сообщения: 15 530

Рейтинг: 0 / 0

Немного потестил. Тоже срочный сервиспак надо :)

Код: plaintext

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.

int is[] = { 4, 4, 3, 3, 2, 1, 1, 1, 2, 2, 3, 4, 4 };

int main()
{
	int* end = is + sizeof(is) / sizeof(is[0]);
	// Поиск 3+ подряд
	int* cur = is + 1;
	int cnt = 1;
	for (; cur < end; cur++) {
		if(*(cur - 1) == *cur) {
			cnt++;
		} else if(cnt >= 3) {
			break;
		} else {
			cnt = 1;
		}
	}
	if(cnt < 3) {
		cnt = 0;
	} else {
		// Схлапывание по краям найденного
		int* left = cur - cnt - 1;
		while(cur < end && left >= is && *left == *cur) {
			int cnt_add = 2;
			// Подсчет влево
			left--;
			if (left >= is && *left == *cur) {
				cnt_add++;
				left--;
			}
			// Подсчет вправо
			cur++;
			if(cur < end && *(cur - 1) == *cur) {
				cnt_add++;
				cur++;
			}
			if (cnt_add < 3) break;
			cnt += cnt_add;
			
		}
	}

	std::cout << cnt << std::endl;
	return 0;
}

получилась тоже что и у тебя с рекурсией, только цикл вместо рекурсии.

...

Рейтинг:

0 / 0

20.03.2016, 18:48

| Ответить | Цитировать | Написать

Шарики(задача по программированию)

#39196633

Siemargl

Участник

Откуда: 010100

Сообщения: 6 423

Рейтинг: 0 / 0

Dima T,

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

что то типа /Ox /G7 /Oy

...

Рейтинг:

0 / 0

20.03.2016, 22:52

| Ответить | Цитировать | Написать

18 сообщений из 93, страница 4 из 4

все

Форумы / C++ [игнор отключен] [закрыт для гостей] / Шарики(задача по программированию)

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=57&gotonew=1&tid=2018575]:	0ms
get settings:	12ms
get forum list:	11ms
check forum access:	4ms
check topic access:	4ms
track hit:	48ms
get topic data:	12ms
get first new msg:	9ms
get forum data:	3ms
get page messages:	63ms
get tp. blocked users:	1ms
others:	10ms

total:	177ms