Dynamic programming. Recursion. Loops.

[hentaimean]

Hello! Please tell me how to implement an algorithm with recursion using loops.

"main.cpp"

#include<iostream>
#include "methods.h"
 
int N, M, *a, **mas_res, n_res, Res{-1}, **mas_temp, n_temp{0};
 
void alg_1(int Sum, int i){
    if(i == N){
        if(Res == -1){
            for(int j{}; j < n_temp; j++){
                mas_res[j][0] = mas_temp[j][0];
                mas_res[j][1] = mas_temp[j][1];
            }
            n_res = n_temp;
            mas_res[n_res - 1][1] = N;
            Res = Sum;
        }
 
        else{
            if(Res > Sum){
                for(int j{}; j < n_temp; j++){
                    mas_res[j][0] = mas_temp[j][0];
                    mas_res[j][1] = mas_temp[j][1];
                }
                n_res = n_temp;
                Res = Sum;
                mas_res[n_res - 1][1] = N;
            }
        }
    }
 
    int temp{0};
    for(int j = i; j < N; j++){
        temp += a[j] * (j - i + 1);
        if(n_temp < M - 1 || (n_temp == M - 1 && j + 1 == N)){
            mas_temp[n_temp++][1] = j + 1;
            if(n_temp < M)
                mas_temp[n_temp][0] = j + 2;
            Sum = Sum + temp;
            i = j + 1;
            alg_1(Sum, i); //recursion
            n_temp--;
        }
    }
}
 
int main(){
    std::cout << "Enter number of buttons and number of letters:" << std::endl;
    std::cin >> N >> M;
 
    a = new int[N];
    mas_res = new int*[M];
    mas_temp = new int*[M];
 
    for(int i{}; i < M; i++){
        mas_res[i] = new int[2];
        mas_temp[i] = new int[2];
    }
 
    fill(N, a);
 
    mas_temp[0][0] = 1;
 
    alg_1(0, 0);
    print(Res, n_res, mas_res);
 
    for (int i{}; i < M; i++){
        delete [] mas_res[i];
        delete [] mas_temp[i];
    }
 
    delete [] mas_res;
    delete [] mas_temp;
    return 0;
}

"methods.h"

#ifndef PROG_5_METHODS_H
#define PROG_5_METHODS_H
 
#include <iostream>
 
void fill(int N, int *a) {
    for(int i{}; i < N; i++) {
        std::cout << "Enter the frequency of letter " << i + 1 << ":" << std::endl;
        std::cin >> a[i];
    }
}
 
void print(int Res, int n_res, int **mas_res) {
    std::cout << "\nMinimum characteristic = " << Res << std::endl;
 
    for(int i{}; i < n_res; i++) {
        std::cout << "The range of characters associated with the key " << i + 1 << ":" << std::endl;
        std::cout << mas_res[i][0] << " " << mas_res[i][1] << std::endl;
    }
}
 
#endif //PROG_5_METHODS_H 

Example:
Entrance:

5 3
3
2
5
7
1

Output:

21
1 2
3 3
4 5

If anybody could help me that would be great, thank you very much in advance!

[jonnin]

Hey! I am fairly lazy when it comes to other people's work, so I will ask instead of trying to unravel what you did and figure it out.

what is the algorithm, what does it do, does it have a name, etc?

that said, recursion has 2 frequent uses:
1) it gives you a 'free' stack like structure.
2) it frequently shortens code by hiding the main loop (the recursion itself) and the stack 'container', cutting small routines in half as often as not.

making code shorter has merits, but recursion takes extra time and energy for even experienced coders to read and follow. I usually only use it when the size reduction is substantial or the free stack is a huge bonus.
...Looping with recursion is a headache to follow in complex algorithms. The recursion itself is a loop, as I said, so its N*N type looping but the outer loop is hiding ...
anyway, tell us what the thing does and all please!

[hentaimean]

I need to solve the problem in three different ways: using recursion, loops, and memoization. I've already dealt with recursion, but I can't replace it with loops.

Here is the text of the problem:
There is the following way to type letters on a mobile phone. Key 2 is mapped to letters abc, key 3 def, etc. When typing, one press on key 2 generates symbol a, two consecutive pressings of symbol b, three in a row symbol c; similarly, one press on 3 generates d, two in a row e, etc. If you need to type two letters a, then click on 2, wait a little and click on 2 again.
Let's summarize the situation. Let there be an alphabet of N characters that you want to associate with M keys (M <N). For each character of the alphabet, the frequency of its use is known. It is necessary to set the correspondence of alphabet characters to keys so that characters from the first to some k1-st correspond to the first key, from the (k1 + 1)-th to some k2-nd second key, etc., and the average number of keystrokes (based on of the known frequencies) was minimal. Formally speaking, it is necessary to minimize the characteristic (the sum of i from 1 to N from (Fi * Ti)), where Fi is the frequency of using the i-th character according to the input data, Ti is the number of clicks required to set the i-th character according to the constructed alphabet partition.

Entrance. The first line of text contains N and M, the next N lines contain one integer proportional to the frequency of using the character (2 < M ≤ 100, M < N ≤ 250).

Output. The first line of text should contain the found minimum characteristic, and each of the next M lines should contain two numbers (a space between them) that specify the range of characters associated with this key.

[jonnin]

if you want to minimize the button press, why isnt the first letter associated to a button defaulted so if they hit another button its done?
eg
press 2, 33 and that is "ae" (2 defaults to a because pressed once, 3 twice is e from def)

that aside..
loops... I dunno, maybe:
for(all the buttons)
if button pressed is true
for the number of times it is pressed again (or while...) ... it can be pressed 0 times do nothing in that case?
iterate the list of letters it can be. if reached end, pick last letter and kick out

something like that??
personally i would have a lookup table of what letters can be under a key press, and just one loop iterate those. Is a single loop enough for the professor?

[hentaimean]

Thanks for the hint on how to minimize button clicks. I just followed the given example of the output and therefore did not think to do as you said.)

About lookup table using one loop. It won't quite work. The fact is that with the help of loops I need to implement the most inefficient algorithm in order to compare its running time with others. So I need to use a lot of loops and conditions. How can this be done?

[hentaimean]

Although no, you're right, here you can really try to do as you said. Could you please tell me in more detail about how you would have done using the lookup table? Just I don't quite understand. How fast would such an algorithm be?

[helios]

There's no such thing as the most inefficient algorithm for a given problem. As long as it eventually terminates, you can continue adding superfluous steps.

[hentaimean]

OK I understood. Then tell me, please, could you suggest how best to implement an algorithm that in this situation will be less efficient or approximately the same in speed?

[dhayden]

I think Jonnin misunderstood the problem. It sounds like he's thinking of ways to decode the button presses. The problem is actually about how to layout the letters on the keyboard to mimimize the total number of presses over time.

Hentaimean, you've shown your code and you've shown the problem. What is your algorithm? It's hard to know how to convert your code to loops without understanding how it works.

[dutch]

Your recursive code is incorrect. Take the following input:

10 5
3 2 5 7 1 2 1 4 2 5

Your code yields:

47
1 1
2 3
4 4
5 8
9 10

But the "button sum" of that layout is actually 58:

         3 2 5 7 1 2 1 4 2 5
1 1      1                    =   3
2 3        1 2                =  12
4 4            1              =   7
5 8              1 2 3 4      =  24
9 10                     1 2  =  12
                                ===
                                 58

An optimal answer is:

44
1 2
3 3
4 7
8 9
10 10

         3 2 5 7 1 2 1 4 2 5
1 2      1 2                  =   7
3 3          1                =   5
4 7            1 2 3 4        =  19
8 9                    1 2    =   8
10 10                      1  =   5
                                ===
                                 44

[lastchance]

Recursion:

#include <iostream>
#include <vector>
using namespace std;

int N, M;


void level( int r, const vector<int> &freq, vector<int> &k, vector<int> &bestk,
            unsigned long long total, unsigned long long &besttotal )          // Insert the k[r]-th key end
{
   if ( r == M )                                                               // Last one must be after the last letter
   {
      for ( int kk = k[r-1] + 1; kk <= N; kk++ ) total += ( kk - k[r-1] ) * freq[kk];
      k[r] = N;
      if ( besttotal == 0 || total < besttotal )                               // Update best-so-far if necessary
      {
         besttotal = total;
         bestk = k;
      }
      return;
   }
   for ( k[r] = k[r-1] + 1; k[r] <= N - M + r; k[r]++ )                        // Or consider all other positions ...
   {
      total += ( k[r] - k[r-1] ) * freq[k[r]];
      level( r + 1, freq, k, bestk, total, besttotal );                        // ... then go to next key
   }
}


int main()
{
   cin >> N >> M;
   vector<int> k(1+M,0), bestk(1+M,0);
   vector<int> freq(1+N,0);
   for ( int i = 1; i <= N; i++ ) cin >> freq[i];

   unsigned long long total = 0, besttotal = 0;
   level( 1, freq, k, bestk, total, besttotal );                               // Start by placing the k[1]-th key end

   cout << besttotal << '\n';
   for ( int i = 1; i <= M; i++ ) cout << bestk[i-1] + 1 << " " << bestk[i] << '\n';
}

With OP's data:

21
1 2
3 3
4 5

With dutch's data:

44
1 2
3 3
4 7
8 9
10 10

[hentaimean]

dutch and lastchance, thanks a lot, saw my mistake and fixed it.

Here's the correct code:

#include<iostream>

int N, M, *a, **mas_res, n_res, Res{-1}, **mas_temp, n_temp{};

void alg_1(int Sum, int i){
    if(i == N){
        if(Res == -1){
            for(int j{}; j < n_temp; j++){
                mas_res[j][0] = mas_temp[j][0];
                mas_res[j][1] = mas_temp[j][1];
            }
            n_res = n_temp;
            mas_res[n_res - 1][1] = N;
            Res = Sum;
        }

        else{
            if(Res > Sum){
                for(int j{}; j < n_temp; j++){
                    mas_res[j][0] = mas_temp[j][0];
                    mas_res[j][1] = mas_temp[j][1];
                }
                n_res = n_temp;
                Res = Sum;
                mas_res[n_res - 1][1] = N;
            }
        }
    }

    int temp{};
    for(int j = i; j < N; j++){
        temp += a[j] * (j - i + 1);
        if(n_temp < M - 1 || (n_temp == M - 1 && j + 1 == N)){
            mas_temp[n_temp++][1] = j + 1;
            if(n_temp < M)
                mas_temp[n_temp][0] = j + 2;
            alg_1(Sum + temp, j + 1);
            n_temp--;
        }
    }
}

int main(){
    std::cin >> N >> M;

    a = new int[N];
    mas_res = new int*[M];
    mas_temp = new int*[M];

    for(int i{}; i < M; i++){
        mas_res[i] = new int[2];
        mas_temp[i] = new int[2];
    }

    for(int i{}; i < N; i++) {
        std::cin >> a[i];
    }

    mas_temp[0][0] = 1;

    alg_1(0, 0);

    std::cout << Res << std::endl;

    for(int i{}; i < n_res; i++) {
        std::cout << mas_res[i][0] << " " << mas_res[i][1] << std::endl;
    }

    for (int i{}; i < M; i++){
        delete [] mas_res[i];
        delete [] mas_temp[i];
    }

    delete [] mas_res;
    delete [] mas_temp;
    return 0;
}

Please tell me how to solve this problem now without recursion so that the speed of the algorithm execution remains approximately the same.

[lastchance]

OK, dynamic programming version:

#include <iostream>
#include <vector>
using namespace std;

int N, M;
using INT = unsigned long long;


int main()
{
   cin >> N >> M;
   vector<int> freq( 1 + N, 0 );
   for ( int i = 1; i <= N; i++ ) cin >> freq[i];

   vector<INT> T( 1 + N, 0ull );       // T[kr] is best total to date concluding at position kr
   vector< vector<int> > prev( 1 + M, vector<int>( 1 + N, 0 ) );

   for ( int r = 1; r <= M; r++ )
   {
      auto oldT = T;
      for ( auto &e : T ) e = 0;
      for ( int krm = r - 1; krm <= ( r == 1 ? 0 : N - M + r - 1 ); krm++ )
      {
         INT test = oldT[krm];
         for ( int kr = krm + 1; kr <= N - M + r; kr++ )
         {
            test += ( kr - krm ) * freq[kr];
            if ( T[kr] == 0 || T[kr] > test )
            {
               T[kr] = test;
               prev[r][kr] = krm;
            }
         }
      }
   }

   vector<int> bestk( 1 + M);
   bestk[M] = N;
   for ( int i = M - 1; i > 0; i-- ) bestk[i] = prev[i+1][bestk[i+1]];

   cout << T[N] << '\n';
   for ( int i = 1; i <= M; i++ ) cout << bestk[i-1] + 1 << " " << bestk[i] << '\n';
}

Result with OP's original data:

21
1 2
3 3
4 5

Result with @dutch's test data:

44
1 2
3 3
4 7
8 9
10 10

[hentaimean]

Oh, thanks a lot!)