Получение ПРЕВЫШЕНИЯ ОГРАНИЧЕНИЯ ВЫХОДА в программе на C++
Решаю проблему Странный алгоритм:
Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this, until n is one. For example, the sequence for n=3 is as follows: 3→10→5→16→8→4→2→1
Your task is to simulate the execution of the algorithm for a given value of n.
Input
The only input line contains an integer n.
Output
Print a line that contains all values of n during the algorithm.
Constraints
1≤n≤10^6
Проблема была решена, но возникла проблема с OUTPUT LIMIT EXCEED. Много искал, но не нашел способа избавиться от этой проблемы.
Он работает нормально, пока я не ввожу = 270271, он дает неожиданный результат, включая отрицательные значения.
#include <iostream>
using namespace std;
void fun(int n) {
if (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
fun(n);
}
}
int main() {
int n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
Как 3 и 6 могут давать разные результаты, если первый шаг из 6 уже дает 3?
Одна из причин превышения производительности - использование рекурсии. Если какое-то число дает очень длинную последовательность, рекурсия вашей программы выйдет за край. Лучше использовать while (n != 1) вместо рекурсии.
@Dominique любезно прочитал набор задач.
@Arty проблема связана с scanf (), если я ввожу 270271, тогда предел вывода превышает, я тоже пробовал с while, но без усиления.
@ShoaibKhalid Тебе действительно стоит сосредоточиться на WRONG ANSWER. Сначала исправьте их, и, возможно, остальные проблемы исчезнут сами собой.
@PaulMcKenzie, мне интересно, когда я запускаю на своем ПК, все выходы работают отлично, кроме тех, где OUPUT LIMIT EXCEED
Посмотрим, сможешь ли ты украсть входной набор. Также не забывайте, что если у вас есть какой-либо неопределенное поведение в коде, например, переполнение стека из-за избыточной рекурсии, обычным результатом является различное поведение на разных машинах.
int64_t вместо int для используемых вами целочисленных типов. Скорее всего, у вас целочисленное переполнение.
Ответы 1
Постарайтесь не использовать здесь рекурсию, это может привести к сбою вашего двоичного файла, если глубина рекурсии слишком велика, а последовательность Коллатца иногда может быть очень длинной, попробуйте вместо этого использовать цикл while. Переполнение стека может привести к чрезмерному выходу.
Также на некоторых входах может быть переполнение int. Вместо этого используйте uint64_t. Как в моем коде ниже.
Полностью исправленная программа:
#include <iostream>
#include <cstdint>
using namespace std;
void fun(uint64_t n) {
while (n != 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n *= 3;
n++;
}
cout << " " << n;
}
}
int main() {
uint64_t n;
cin >> n;
cout << " " << n;
fun(n);
return 0;
}
Вход:
270271
Выход:
270271 810814 405407 1216222 608111 1824334 912167 2736502 1368251 4104754 2052377 6157132 3078566 1539283 4617850 2308925 6926776 3463388 1731694 865847 2597542 1298771 3896314 1948157 5844472 2922236 1461118 730559 2191678 1095839 3287518 1643759 4931278 2465639 7396918 3698459 11095378 5547689 16643068 8321534 4160767 12482302 6241151 18723454 9361727 28085182 14042591 42127774 21063887 63191662 31595831 94787494 47393747 142181242 71090621 213271864 106635932 53317966 26658983 79976950 39988475 119965426 59982713 179948140 89974070 44987035 134961106 67480553 202441660 101220830 50610415 151831246 75915623 227746870 113873435 341620306 170810153 512430460 256215230 128107615 384322846 192161423 576484270 288242135 864726406 432363203 1297089610 648544805 1945634416 972817208 486408604 243204302 121602151 364806454 182403227 547209682 273604841 820814524 410407262 205203631 615610894 307805447 923416342 461708171 1385124514 692562257 2077686772 1038843386 519421693 1558265080 779132540 389566270 194783135 584349406 292174703 876524110 438262055 1314786166 657393083 1972179250 986089625 2958268876 1479134438 739567219 2218701658 1109350829 3328052488 1664026244 832013122 416006561 1248019684 624009842 312004921 936014764 468007382 234003691 702011074 351005537 1053016612 526508306 263254153 789762460 394881230 197440615 592321846 296160923 888482770 444241385 1332724156 666362078 333181039 999543118 499771559 1499314678 749657339 2248972018 1124486009 3373458028 1686729014 843364507 2530093522 1265046761 3795140284 1897570142 948785071 2846355214 1423177607 4269532822 2134766411 6404299234 3202149617 9606448852 4803224426 2401612213 7204836640 3602418320 1801209160 900604580 450302290 225151145 675453436 337726718 168863359 506590078 253295039 759885118 379942559 1139827678 569913839 1709741518 854870759 2564612278 1282306139 3846918418 1923459209 5770377628 2885188814 1442594407 4327783222 2163891611 6491674834 3245837417 9737512252 4868756126 2434378063 7303134190 3651567095 10954701286 5477350643 16432051930 8216025965 24648077896 12324038948 6162019474 3081009737 9243029212 4621514606 2310757303 6932271910 3466135955 10398407866 5199203933 15597611800 7798805900 3899402950 1949701475 5849104426 2924552213 8773656640 4386828320 2193414160 1096707080 548353540 274176770 137088385 411265156 205632578 102816289 308448868 154224434 77112217 231336652 115668326 57834163 173502490 86751245 260253736 130126868 65063434 32531717 97595152 48797576 24398788 12199394 6099697 18299092 9149546 4574773 13724320 6862160 3431080 1715540 857770 428885 1286656 643328 321664 160832 80416 40208 20104 10052 5026 2513 7540 3770 1885 5656 2828 1414 707 2122 1061 3184 1592 796 398 199 598 299 898 449 1348 674 337 1012 506 253 760 380 190 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
Что, если ввод: 270271?
@Arty - ваш вывод становится отрицательным, что указывает на какое-то целочисленное переполнение.
TL; DR: гипотеза Коллатца