Friends, I'm exploring now binary search (only for ordered arrays). Can for this:

  1. sort an array of random numbers.
  2. output an array using a loop, multiplying any digit by the next array index (this is in ascending order).

I want to derive an array of random numbers, skipping numbers that violate the order of increasing / decreasing. Half a day I dig out - it does not work, although at first glance it is simple. Mozh who will prompt. Thank.

  • And what should be prompted? - alexlz
  • Such questions usually mean: "Can someone write for me?" - andrybak
  • 2
    I think it’s impossible to get a uniformly distributed set, since each subsequent number will depend on the previous one. - skegg
  • @ Key, please explain, sorting why not suitable? In the end, you can sort by inserts, during the formation of the array and for example, if necessary, discard duplicates. - avp

6 answers 6

Can so

bool rand_fill (int * arr, int arr_size){ #if RAND_MAX < INT_MAX if (arr_size > RAND_MAX) return false; #endif srand (time(NULL)); arr[0] = rand()/arr_size; for (int i = 0; i < arr_size - 1; i++) { arr[i+1] = rand() % (RAND_MAX - arr[i] - arr_size + i + 2) + arr[i] + 1; } return true; }
  • 2
    Although, of course, all this is a perversion. It is better to get an array of arbitrary randoms and then sort it. - skegg 4:08 pm

The first term in the sequence is obtained by randomization. Each subsequent - random + previous + 1 (if needed, so that it would be guaranteed more)

  • 3
    If you do not limit the values ​​obtained by random (), the overflow will occur very quickly, the next "next" will be less than the previous one. - avp
  • It all depends on the implementation of the randomization :) I did not write that it is necessary to use random () (by the way, there is no such function, there is a rand ()). But if you use rand (), then yes, the overflow will be fast. - KoVadim
  • In most * nix, random () is primary. For evenly distributed numbers (this is what the generator implements), IMHO (on average) will be added RAND_MAX / 2 at each step. By the way, rand () and random () in Linux are the same function. - avp
  • And there are some nice files in / nix / dev / rand and / dev / srand ... - skegg
  • one
    @avp void question (OS system = Windows); - skegg

In the question the keywords "skipping numbers that violate the ascending / descending order", i.e. array is already full. In general, the task is to find the largest increasing / decreasing subsequence, here is the algorithm for finding the longest increasing subsequence in a quadratic time, there is a method for n * log (x), if you need to google

 int d[MAXN], p[MAXN]; // константа MAXN равна наибольшему возможному значению n for (int i=0; i<n; ++i) { d[i] = 1; p[i] = -1; for (int j=0; j<i; ++j) if (a[j] < a[i]) if (1 + d[j] > d[i]) { d[i] = 1 + d[j]; p[i] = j; } } int ans = d[0], pos = 0; for (int i=0; i<n; ++i) if (d[i] > ans) { ans = d[i]; pos = i; } cout << ans << endl; vector<int> path; while (pos != -1) { path.push_back (pos); pos = p[pos]; } reverse (path.begin(), path.end()); for (int i=0; i<(int)path.size(); ++i) cout << path[i] << ' ';

    Thanks for the answers and comments. Andrei wrote to me: Such questions usually mean: "Maybe someone will write for me?" No, Andrei, I do not need to give someone else for my own, I am 52 years old, I do not study in any educational institution. My goal is to learn myself, including through the work of other people. When I started learning C ++ (I have now mastered 11 lessons from 22), I tried to solve everything myself, in the end I spent a lot of time, in particular, the problem “How to become a millionaire” (TV game), I did more than a month (almost puffed over this task every day) and although it is a huge benefit from this, even if we spend time so much, it’s superfluous. Now, if something relatively quickly does not work, I’m looking for an answer in the Internet (only to save time), then I try to work it out to automatism. About my question. There are your answers that, in order to understand, I just don’t have enough knowledge. The smartest answer was given to me by Mikillskegg, everything is very clear, but I found a pitfall in this algorithm: let's say we make an array in ascending order, if the first or any (by index) random number is the maximum possible number of the rand () range, no further increase will be possible. Why it was in this way that I decided to derive an ordered sequence from random numbers, because there are other ways, just testing different methods. Here I discovered the underwater stone - use.

    • Respect for the fact that despite their age they took up a new business. But I made the program so that the error you indicated does not happen. Read the code more closely. Never be the same numbers. If you do not understand, if possible, I will explain. - skegg pm
    • Well done @ Key! @mikillskegg, in RAND_MAX = 32767 in Windows. Something I wondered what would happen for arr_size> RAND_MAX? - avp
    • You can simply enter a check at the beginning of the function to arr_size <= RAND_MAX. Otherwise, you just can’t do what @ Key wants. I actually inserted such a check first, then removed it, because I thought that the size of RAND_MAX is the same everywhere as in line, i.e. == INT_MAX. And what wrote @Key will not happen in my algorithm. You can check. I considered this option. @avp, you, I think, are quite able to figure out the basis of the program text. - skegg
    • I won’t find what I wrote @ Key, but it seems to me that with a large arr_size, the sequentially calculated sums of all rand () will be placed in the array elements. Overflow for RAND_MAX = 32767 will occur (?) I do not think. - avp
    • Well, yes, for large arr_size, there will initially be several arbitrary values, and then just consecutive numbers will go. With arr_size ==, the RAND_MAX array will be filled with consecutive numbers from 1 to RAND_MAX or from 0 to RAND_MAX-1 (but this case will be very rare in this algorithm). - skegg 4:04 pm

    The first member of the array is random (10), the second is random (20) +10, and so on in a loop.

    • Rather, random (10) +10. =) Although still quite clumsy. - ling
    • Dear mikillskegg, I don’t understand your code on this page due to lack of knowledge. Hashcode sent me another version of your code, for some reason it is not on this page, it is clear to me, though I redid it in my own way took only the idea. Inside the for loop, using the do {...} while loop using its corresponding condition, we select the necessary numbers and print them with the outer for loop. In which of your two codes does the indicated error not occur? - Key
    • The code now lying on the site is more correct. What exactly is not clear? - skegg

    Another option

     #include <stdio.h> #include <stdlib.h> #include <limits.h> int fill (int *a, int size) { if (size < 1) return 0; int i, d = INT_MAX/size; a[0] = rand()%d; for (i = 1; i < size; i++) a[i] = a[i-1] + rand()%d +1; return 1; } main (int ac, char *av[]) { int n = 10; if (ac > 1) if ((n = atoi(av[1])) <= 0) n = 1; int i, *a = malloc(n*sizeof(*a)); srand(time(0)); fill(a,n); for (i = 0; i < ((n > 3)? 3:n); i++) printf ("a[%d] %d\n",i,a[i]); if (n > 3) for (i = n-2; i < n; i++) printf ("a[%d] %d\n",i,a[i]); }

    Next, a wide field to modify fill () (you can add min, max or limit d, etc.).

    Practice @ Key .

    • To compile g ++, add: #include <time.h> and correct ... * a = malloc (... by: ... * a = (int *) malloc (... - avp