足のコードを探します(C百例、半分を折ります&&時を測ります)
6798 ワード
問題は以上の通りです.順序付けされているため、効率性を向上させるために、折半検索(二分)を容易に連想できます.次に、一般的な方法と折半を比較します.テストデータ:
10000000
0 1 2 …… 97 99 200 202……20000000
1000 1 2 3 …… 1000
一般的な方法で比較:
99
条件を満たすのは1つ、時間:0.055000,000
1 2 3 …… 999 1000
条件を満たすものは1000個、時間:0.00100000
半分に折ります.
99
条件を満たすのは1つで、時間:0.0000000
500 250 125 62 31 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30 46 38 34 32 33 36 35 37 42 40 39 41 44 43 45 54 50 48 47 49 52 51 53 58 56 55 57 60 59 61 93 77 69 65 63 64 67 66 68 73 71 70 72 75 74 76 85 81 79 78 80 83 82 84 89 87 86 88 91 90 92 109 101 97 95 94 96 99 98 100 105 103 102 104 107 106 108 117 113 111 110 112 115 114 116 121 119 118 120 123 122 124 187 156 140 132 128 126 127 130 129 131 136 134 133 135 138 137 139 148 144 142 141 143 146 145 147 152 150 149 151 154 153 155 171 163 159 157 158 161 160 162 167 165 164 166 169 168 170 179 175 173 172 174 177 176 178 183 181 180 182 185 184 186 218 202 194 190 188 189 192 191 193 198 196 195 197 200 199 201 210 206 204 203 205 208 207 209 214 212 211 213 216 215 217 234 226 222 220 219 221 224 223 225 230 228 227 229 232 231 233 242 238 236 235 237 240 239 241 246 244 243 245 248 247 249 375 312 281 265 257 253 251 252 255 254 256 261 259 258 260 263 262 264 273 269 267 266 268 271 270 272 277 275 274 276 279 278 280 296 288 284 282 283 286 285 287 292 290 289 291 294 293 295 304 300 298 297 299 302 301 303 308 306 305 307 310 309 311 343 327 319 315 313 314 317 316 318 323 321 320 322 325 324 326 335 331 329 328 330 333 332 334 339 337 336 338 341 340 342 359 351 347 345 344 346 349 348 350 355 353 352 354 357 356 358 367 363 361 360 362 365 364 366 371 369 368 370 373 372 374 437 406 390 382 378 376 377 380 379 381 386 384 383 385 388 387 389 398 394 392 391 393 396 395 397 402 400 399 401 404 403 405 421 413 409 407 408 411 410 412 417 415 414 416 419 418 420 429 425 423 422 424 427 426 428 433 431 430 432 435 434 436 468 452 444 440 438 439 442 441 443 448 446 445 447 450 449 451 460 456 454 453 455 458 457 459 464 462 461 463 466 465 467 484 476 472 470 469 471 474 473 475 480 478 477 479 482 481 483 492 488 486 485 487 490 489 491 496 494 493 495 498 497 499 750 625 562 531 515 507 503 501 502 505 504 506 511 509 508 510 513 512 514 523 519 517 516 518 521 520 522 527 525 524 526 529 528 530 546 538 534 532 533 536 535 537 542 540 539 541 544 543 545 554 550 548 547 549 552 551 553 558 556 555 557 560 559 561 593 577 569 565 563 564 567 566 568 573 571 570 572 575 574 576 585 581 579 578 580 583 582 584 589 587 586 588 591 590 592 609 601 597 595 594 596 599 598 600 605 603 602 604 607 606 608 617 613 611 610 612 615 614 616 621 619 618 620 623 622 624 687 656 640 632 628 626 627 630 629 631 636 634 633 635 638 637 639 648 644 642 641 643 646 645 647 652 650 649 651 654 653 655 671 663 659 657 658 661 660 662 667 665 664 666 669 668 670 679 675 673 672 674 677 676 678 683 681 680 682 685 684 686 718 702 694 690 688 689 692 691 693 698 696 695 697 700 699 701 710 706 704 703 705 708 707 709 714 712 711 713 716 715 717 734 726 722 720 719 721 724 723 725 730 728 727 729 732 731 733 742 738 736 735 737 740 739 741 746 744 743 745 748 747 749 875 812 781 765 757 753 751 752 755 754 756 761 759 758 760 763 762 764 773 769 767 766 768 771 770 772 777 775 774 776 779 778 780 796 788 784 782 783 786 785 787 792 790 789 791 794 793 795 804 800 798 797 799 802 801 803 808 806 805 807 810 809 811 843 827 819 815 813 814 817 816 818 823 821 820 822 825 824 826 835 831 829 828 830 833 832 834 839 837 836 838 841 840 842 859 851 847 845 844 846 849 848 850 855 853 852 854 857 856 858 867 863 861 860 862 865 864 866 871 869 868 870 873 872 874 938 906 890 882 878 876 877 880 879 881 886 884 883 885 888 887 889 898 894 892 891 893 896 895 897 902 900 899 901 904 903 905 922 914 910 908 907 909 912 911 913 918 916 915 917 920 919 921 930 926 924 923 925 928 927 929 934 932 931 933 936 935 937 969 953 945 941 939 940 943 942 944 949 947 946 948 951 950 952 961 957 955 954 956 959 958 960 965 963 962 964 967 966 968 985 977 973 971 970 972 975 974 976 981 979 978 980 983 982 984 993 989 987 986 988 991 990 992 997 995 994 996 999 998 1000
条件を満たすものは1000個、時間:0.0000000
ふふ、折半出力での結果は順番検索ほど単調性がないので、前の出力のように「・・・」とは表現できません.運行時間から見れば、折りたたみがもっと素晴らしいです.2つ目の例の半分も0.0000000であり、実際にfindの呼び出し回数をカウントするのは2001であるが、順序検索よりも時間が短く、これは分而治の役割を果たしている.
#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=1e7;
int main(){
freopen("cout.txt","w",stdout);
cout<<maxn<<endl;
for(int i=1;i<99;i++){
printf("%d ",i-1);
}
printf("99 ");
for(int i=100;i<=maxn;i++){
printf("%d ",i*2);
}
cout<<endl<<1000<<endl;
for(int i=1;i<=1000;i++){
printf("%d ",i);
}
return 0;
} 10000000
0 1 2 …… 97 99 200 202……20000000
1000 1 2 3 …… 1000
一般的な方法で比較:
#include <iostream>
#include<cstdio>
#include<time.h>
using namespace std;
const int maxn=1e7+5;
int number[maxn],sum;
int main(){
freopen("cin.txt","r",stdin);
freopen("cout.txt","w",stdout);
int n;
while(cin>>n){
for(int i=1;i<=n;i++)scanf("%d",&number[i]);
sum=0;
clock_t start,finish; //
start=clock();
for(int i=1;i<=n;i++){
if(number[i]==i){
printf("%d ",i);
sum++;
}
}
finish=clock();
printf("
%d ,",sum);
printf(" ：%.8lf
",(double)(finish-start)/CLOCKS_PER_SEC);
//CLOCKS_PER_SEC
}
return 0;
}
99
条件を満たすのは1つ、時間:0.055000,000
1 2 3 …… 999 1000
条件を満たすものは1000個、時間:0.00100000
半分に折ります.
#include <iostream>
#include<cstdio>
#include<time.h>
using namespace std;
const int maxn=1e7+5;
int number[maxn],length,sum; //low don't find low dex, high don't find high dex.
void find(int low,int high){
if(low>high)return ;
int dex=(low+high)/2;
if(number[dex]==dex){
printf("%d ",dex);
sum++;
find(low,dex-1);
find(dex+1,high);
}
else if(number[dex]<dex) find(dex+1,high);
else find(low,dex-1);
}
int main()
{
freopen("cin.txt","r",stdin);
freopen("cout.txt","w",stdout);
int n;
while(cin>>n){
sum=0;
for(int i=1;i<=n;i++)scanf("%d",&number[i]);
clock_t start,finish;
int low,high;
low=1; high=n;
start=clock();
find(low,high);
finish=clock();
printf("
%d ,",sum);
printf(" ：%.8f
",(double)(finish-start)/CLOCKS_PER_SEC);
}
return 0;
}99
条件を満たすのは1つで、時間:0.0000000
500 250 125 62 31 15 7 3 1 2 5 4 6 11 9 8 10 13 12 14 23 19 17 16 18 21 20 22 27 25 24 26 29 28 30 46 38 34 32 33 36 35 37 42 40 39 41 44 43 45 54 50 48 47 49 52 51 53 58 56 55 57 60 59 61 93 77 69 65 63 64 67 66 68 73 71 70 72 75 74 76 85 81 79 78 80 83 82 84 89 87 86 88 91 90 92 109 101 97 95 94 96 99 98 100 105 103 102 104 107 106 108 117 113 111 110 112 115 114 116 121 119 118 120 123 122 124 187 156 140 132 128 126 127 130 129 131 136 134 133 135 138 137 139 148 144 142 141 143 146 145 147 152 150 149 151 154 153 155 171 163 159 157 158 161 160 162 167 165 164 166 169 168 170 179 175 173 172 174 177 176 178 183 181 180 182 185 184 186 218 202 194 190 188 189 192 191 193 198 196 195 197 200 199 201 210 206 204 203 205 208 207 209 214 212 211 213 216 215 217 234 226 222 220 219 221 224 223 225 230 228 227 229 232 231 233 242 238 236 235 237 240 239 241 246 244 243 245 248 247 249 375 312 281 265 257 253 251 252 255 254 256 261 259 258 260 263 262 264 273 269 267 266 268 271 270 272 277 275 274 276 279 278 280 296 288 284 282 283 286 285 287 292 290 289 291 294 293 295 304 300 298 297 299 302 301 303 308 306 305 307 310 309 311 343 327 319 315 313 314 317 316 318 323 321 320 322 325 324 326 335 331 329 328 330 333 332 334 339 337 336 338 341 340 342 359 351 347 345 344 346 349 348 350 355 353 352 354 357 356 358 367 363 361 360 362 365 364 366 371 369 368 370 373 372 374 437 406 390 382 378 376 377 380 379 381 386 384 383 385 388 387 389 398 394 392 391 393 396 395 397 402 400 399 401 404 403 405 421 413 409 407 408 411 410 412 417 415 414 416 419 418 420 429 425 423 422 424 427 426 428 433 431 430 432 435 434 436 468 452 444 440 438 439 442 441 443 448 446 445 447 450 449 451 460 456 454 453 455 458 457 459 464 462 461 463 466 465 467 484 476 472 470 469 471 474 473 475 480 478 477 479 482 481 483 492 488 486 485 487 490 489 491 496 494 493 495 498 497 499 750 625 562 531 515 507 503 501 502 505 504 506 511 509 508 510 513 512 514 523 519 517 516 518 521 520 522 527 525 524 526 529 528 530 546 538 534 532 533 536 535 537 542 540 539 541 544 543 545 554 550 548 547 549 552 551 553 558 556 555 557 560 559 561 593 577 569 565 563 564 567 566 568 573 571 570 572 575 574 576 585 581 579 578 580 583 582 584 589 587 586 588 591 590 592 609 601 597 595 594 596 599 598 600 605 603 602 604 607 606 608 617 613 611 610 612 615 614 616 621 619 618 620 623 622 624 687 656 640 632 628 626 627 630 629 631 636 634 633 635 638 637 639 648 644 642 641 643 646 645 647 652 650 649 651 654 653 655 671 663 659 657 658 661 660 662 667 665 664 666 669 668 670 679 675 673 672 674 677 676 678 683 681 680 682 685 684 686 718 702 694 690 688 689 692 691 693 698 696 695 697 700 699 701 710 706 704 703 705 708 707 709 714 712 711 713 716 715 717 734 726 722 720 719 721 724 723 725 730 728 727 729 732 731 733 742 738 736 735 737 740 739 741 746 744 743 745 748 747 749 875 812 781 765 757 753 751 752 755 754 756 761 759 758 760 763 762 764 773 769 767 766 768 771 770 772 777 775 774 776 779 778 780 796 788 784 782 783 786 785 787 792 790 789 791 794 793 795 804 800 798 797 799 802 801 803 808 806 805 807 810 809 811 843 827 819 815 813 814 817 816 818 823 821 820 822 825 824 826 835 831 829 828 830 833 832 834 839 837 836 838 841 840 842 859 851 847 845 844 846 849 848 850 855 853 852 854 857 856 858 867 863 861 860 862 865 864 866 871 869 868 870 873 872 874 938 906 890 882 878 876 877 880 879 881 886 884 883 885 888 887 889 898 894 892 891 893 896 895 897 902 900 899 901 904 903 905 922 914 910 908 907 909 912 911 913 918 916 915 917 920 919 921 930 926 924 923 925 928 927 929 934 932 931 933 936 935 937 969 953 945 941 939 940 943 942 944 949 947 946 948 951 950 952 961 957 955 954 956 959 958 960 965 963 962 964 967 966 968 985 977 973 971 970 972 975 974 976 981 979 978 980 983 982 984 993 989 987 986 988 991 990 992 997 995 994 996 999 998 1000
条件を満たすものは1000個、時間:0.0000000
ふふ、折半出力での結果は順番検索ほど単調性がないので、前の出力のように「・・・」とは表現できません.運行時間から見れば、折りたたみがもっと素晴らしいです.2つ目の例の半分も0.0000000であり、実際にfindの呼び出し回数をカウントするのは2001であるが、順序検索よりも時間が短く、これは分而治の役割を果たしている.