Problems(I need at least 2 of these solved)

1 |

================================================================================

[25=25] Searching: **** Application, Code Writing (Linguistics). Write a

function int find(string needle, string haystack) to find the first occurrence

of the string needle in the string haystack. It should return the index of

the first character in haystack where the string needle matches, and -1 if

it is not found. Call this find-substring.cpp [-5]. You need only write the

function and test it in the main() as below (it should output the value 5).

--------------------------------------------------------------------------------

1: int main() {

2: cout << find("pill", "caterpillar") << endl;

3: }

--------------------------------------------------------------------------------

================================================================================

-----

2 |

================================================================================

[25=25] Searching: **** Application, Code Writing (Geography). The file

capitals.dat contains capital cities of the U.S. Write a program which, given

latitude (x1) and longitude (y1), finds the closest capital city using a

Euclidean distance approximation sqrt((x2-x1)^2+(y2-y1)^2). Call this

nearest-city.cpp [-5].

Fun fact: if you were to add the coordinates for all cities in the world and

interface the program with GPS or a position sensor, it would be able to find

any nearest city in the world.

--------------------------------------------------------------------------------

1: x> 30.0

2: y> -91.0

3: < Baton_Rouge

--------------------------------------------------------------------------------

================================================================================

-----

3 |

================================================================================

[25=25] Searching: **** Application, Code Writing (Mathematics). Write a code

with function float local_max(float a, float b, float e) which returns the

x-position of the first local maximum of the function float f(float x)

(defined below) in the range [a, b]. The x-value returned should be precise to

e; x is a local maximum of f(x) iff f(x-e)<f(x)>f(x+e). A call to

local_max(1.0, 2.0, .01) gives the local maximum in the domain [1.0, 2.0]

precise to .01 (or 1e-2), which is .54. Call this local-max.cpp [-5]. I/O

interaction looks like this:

a> 0.0

b> 1.0

e> .01

< .54

Note that if you replace float f(float x) with any function definition, the

program will work for that function.

--------------------------------------------------------------------------------

1: float f(float x) {

2: return (sqrt(x)-x)*sin(x);

3: }

--------------------------------------------------------------------------------

================================================================================

-----

4 |

================================================================================

[25=25] Searching: **** Application, Code Writing (Physics). There are 8

switches on a wall: x_0, x_1, ... x_i ..., x_7. Let x_i=true if the ith switch

is on, x_i=false if off. There is a light in the room which turns on if and

only if the following condition is satisfied:

((x_0 or x_1)

and

((x_3 or x_4) or (x_5 and x_6))

and

(x_7 or x_8))

Write a program to list all possible combinations of switches which turn the

light on. See the code c++/searching/which-switches.skel for a template.

Write a function void convert(int n, bool x[]) which converts an integer n,

0<=n<=255, into the boolean array x[]; then use the pseudocode below to write

the main() method. Call this which-switches.cpp [-5].

Effectively this is a search. We try all combinations of boolean arrays; if a

combination works, we print out its configuration.

--------------------------------------------------------------------------------

1: Where n is an integer and x is a boolean array,

2: define Algorithm Find Switches(n, x):

3: For i in range [0, n):

4: Call convert(n, x).

5: If lightup(x):

6: Call print_switches(x).

--------------------------------------------------------------------------------

================================================================================

Skeletons for the problems((not in order, see file name to find order)

[Code 1-1-1]: c++/searching/which-switches.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: #include <iomanip>

3: #include <climits>

4: #include <cmath>

5: #include <algorithm>

6: using namespace std;

7:

8: #define N 8

9:

10:

11: void print_switches(int n, bool x[]) {

12: cout << setw(5) << n;

13: for (int i=0; i<N; i++)

14: cout << setw(5) << ((x

*==true) ? '*' : ' ');*

15: cout << endl;

16: }

17:

18:

19: void convert(int n, bool x[]) {

20: ___ (___ _=N-1; _>=0; _--)

21: __ (_ >= ___(2, _)) {

22: _ -= ___(2, _);

23: _[_] = ____;

24: } ____ _[_] = _____;

25: }

26:

27:

28:

29: bool lightup(bool x[]) {

30: if (

31: (

32: x[0]

33: ||

34: x[1]

35: )

36: &&

37: (

38: (

39: x[3]

40: ||

41: x[4]

42: )

43: ||

44: (

45: x[5]

46: &&

47: x[6]

48: )

49: )

50: &&

51: (

52: x[7]

53: ||

54: x[8]

55: )

56: ) return true;

57: else return false;

58: }

59:

60:

61: int main() {

62: ___ _;

63: ____ _[N];

64: ___ (_=0; _<256; _++) {

65: _______(_, _);

66: __ (_______(_))

67: ______________(_, _);

68: }

69: }

70:

71:

72:

--------------------------------------------------------------------------------

[Line 11]: The function print_switches accepts an integer n and boolean array

x[]. [Line 12]: The integer is right-aligned in a width-5 box. [Line 13]: For

each integer i in range [0, n): [Line 14]: If the switch is on, print a '*',

otherwise a ' ', in a width-5 box. [Line 19]: The function convert converts

an integer in into a boolean array x[]. [Line 20]: For each integer i counting

from N-1 down to and including 0, [Line 21]: if n is greater than 2^i, [Line

22]: subtract 2^i from n [Line 23]: and set x

15: cout << endl;

16: }

17:

18:

19: void convert(int n, bool x[]) {

20: ___ (___ _=N-1; _>=0; _--)

21: __ (_ >= ___(2, _)) {

22: _ -= ___(2, _);

23: _[_] = ____;

24: } ____ _[_] = _____;

25: }

26:

27:

28:

29: bool lightup(bool x[]) {

30: if (

31: (

32: x[0]

33: ||

34: x[1]

35: )

36: &&

37: (

38: (

39: x[3]

40: ||

41: x[4]

42: )

43: ||

44: (

45: x[5]

46: &&

47: x[6]

48: )

49: )

50: &&

51: (

52: x[7]

53: ||

54: x[8]

55: )

56: ) return true;

57: else return false;

58: }

59:

60:

61: int main() {

62: ___ _;

63: ____ _[N];

64: ___ (_=0; _<256; _++) {

65: _______(_, _);

66: __ (_______(_))

67: ______________(_, _);

68: }

69: }

70:

71:

72:

--------------------------------------------------------------------------------

[Line 11]: The function print_switches accepts an integer n and boolean array

x[]. [Line 12]: The integer is right-aligned in a width-5 box. [Line 13]: For

each integer i in range [0, n): [Line 14]: If the switch is on, print a '*',

otherwise a ' ', in a width-5 box. [Line 19]: The function convert converts

an integer in into a boolean array x[]. [Line 20]: For each integer i counting

from N-1 down to and including 0, [Line 21]: if n is greater than 2^i, [Line

22]: subtract 2^i from n [Line 23]: and set x

*to 1. [Line 24]: Otherwise*

if n < 2^i, set xif n < 2^i, set x

*to 0. [Line 29]: The function lightup returns true if*

x[] lights up, false otherwise.

[Line 61]: Define the main() method as follows:

[Line 62]: An integer n is declared for looping.

[Line 63]: The boolean array x[N] is declared. It represents the switches.

[Line 64]: For each integer n in the range [0, 256):

[Line 65]: Call convert(n, x).

[Line 66]: If lightup(x):

[Line 67]: Call print_switches(n, x).

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/nearest-city.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: #include <fstream>

3: #include <cmath>

4: #include <cfloat>

5: using namespace std;

6:

7:

8: int main() {

9:

10: ifstream infile;

11: infile.open("capitals.dat");

12:

13: _____ _, _;

14: _____ ____, ____;

15: _____ _;

16: _____ _____ = FLT_MAX;

17: ______ ____,

18: ________;

19:

20:

21: ____ << "_> ";

22: ___ >> ____;

23: ____ << "_> ";

24: ___ >> ____;

25:

26:

27:

28: _____ (______ >> ____ >> _ >> _) {

29: _ = ____(___((____-_),2) + ___((____-_), 2));

30: __ (_ < _____) {

31: _____ = _;

32: ________ = ____;

33: }

34: }

35:

36: cout << " < " << city_min << endl;

37:

38: }

39:

--------------------------------------------------------------------------------

[Line 11]: The file capitals.dat contains tab-delimited entries <name,

latitude, longitude>. [Line 13]: The vars x and y are used to store latitudes

and longitudes read from file. [Line 14]: The vars x_in and y_in are the

entered latitude and longitude. [Line 15]: The var d holds the distance between

the entered location and each location in the file. [Line 16]: The var d_min is

the minimum distance found so far. Set it to maximum possible value. [Line 17]:

The string city holds the current city read from the file. [Line 18]: The

string city_min is the city whose distance is a minimum. [Line 21]: x. [Line

22]: Read in x_in. [Line 23]: Prompt for y. [Line 24]: Read in y_in.

[Line 27]: Define the search algorithm as follows:

[Line 28]: As long as data can be read from the file,

[Line 29]: Calculate Euclidean distance d.

[Line 30]: If d < d_min:

[Line 31]: Set d_min = d.

[Line 32]: Set city_min = city.

[Line 36]: Output city_min.

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/local-max.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: #include <cmath>

3: using namespace std;

4:

5: float f(float x) {

6: return (sqrt(x)-x)*sin(x);

7: }

8:

9: float xmax(float a, float b, float e) {

10: _____ _, ___ = _(_), ____ = _;

11: ___ (_=_+_; _<_-_; _+=_)

12: __ ( _(_-_) < _(_) &&

13: _(_) > _(_+_) )

14: ______ _;

15: }

16:

17: int main() {

18: float a, b, e;

19: cout << "a> "; cin >> a;

20: cout << "b> "; cin >> b;

21: cout << "e> "; cin >> e;

22: cout << " < " << xmax(a, b, e) << endl;

23: }

24:

--------------------------------------------------------------------------------

[Line 9]: Where a, b, and e are floats, define xmax(a, b, e) as follows:

[Line 10]: Let max <- f(a), xmax <- a.

[Line 11]: For float x in the range [a+e, b-e) in increments of e:

[Line 12]: If f(x-e) < f(x) > f(x+e):

[Line 13]: Return x.

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/find-substring.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: using namespace std;

3:

4: int find(string needle, string haystack) {

5: ____ _____;

6: ___ (___ _=0; _<________.____(); _++) {

7: _____ = ____;

8: __ (________.____()-_<______.____())

9: ______ -1;

10: ___ (___ _=0; _<______.____(); _++)

11: __ (________[_+_] != ______[_])

12: _____ = _____;

13: __ (_____) ______ _;

14: }

15: ______ -1;

16: }

17:

18: int main() {

19: cout << find("pill", "caterpillar") << endl;

20: }

21:

--------------------------------------------------------------------------------

[Line 3]: Where n is the size of haystack, and m is the size of needle, and

found is a boolean,

[Line 4]: Define find(needle, haystack) as follows:

[Line 5]:

[Line 6]: For integer i in the range [0, n):

[Line 7]: Let found <- true.

[Line 8]: If (n-i>m):

[Line 9]: Return -1.

[Line 10]: For integer j in the range [0, m):

[Line 11]: If haystack[i+j] != needle[j]:

[Line 12]: Let found <- false.

[Line 13]: If found:

[Line 14]: Return i.

[Line 15]: Return -1.

--------------------------------------------------------------------------------x[] lights up, false otherwise.

[Line 61]: Define the main() method as follows:

[Line 62]: An integer n is declared for looping.

[Line 63]: The boolean array x[N] is declared. It represents the switches.

[Line 64]: For each integer n in the range [0, 256):

[Line 65]: Call convert(n, x).

[Line 66]: If lightup(x):

[Line 67]: Call print_switches(n, x).

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/nearest-city.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: #include <fstream>

3: #include <cmath>

4: #include <cfloat>

5: using namespace std;

6:

7:

8: int main() {

9:

10: ifstream infile;

11: infile.open("capitals.dat");

12:

13: _____ _, _;

14: _____ ____, ____;

15: _____ _;

16: _____ _____ = FLT_MAX;

17: ______ ____,

18: ________;

19:

20:

21: ____ << "_> ";

22: ___ >> ____;

23: ____ << "_> ";

24: ___ >> ____;

25:

26:

27:

28: _____ (______ >> ____ >> _ >> _) {

29: _ = ____(___((____-_),2) + ___((____-_), 2));

30: __ (_ < _____) {

31: _____ = _;

32: ________ = ____;

33: }

34: }

35:

36: cout << " < " << city_min << endl;

37:

38: }

39:

--------------------------------------------------------------------------------

[Line 11]: The file capitals.dat contains tab-delimited entries <name,

latitude, longitude>. [Line 13]: The vars x and y are used to store latitudes

and longitudes read from file. [Line 14]: The vars x_in and y_in are the

entered latitude and longitude. [Line 15]: The var d holds the distance between

the entered location and each location in the file. [Line 16]: The var d_min is

the minimum distance found so far. Set it to maximum possible value. [Line 17]:

The string city holds the current city read from the file. [Line 18]: The

string city_min is the city whose distance is a minimum. [Line 21]: x. [Line

22]: Read in x_in. [Line 23]: Prompt for y. [Line 24]: Read in y_in.

[Line 27]: Define the search algorithm as follows:

[Line 28]: As long as data can be read from the file,

[Line 29]: Calculate Euclidean distance d.

[Line 30]: If d < d_min:

[Line 31]: Set d_min = d.

[Line 32]: Set city_min = city.

[Line 36]: Output city_min.

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/local-max.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: #include <cmath>

3: using namespace std;

4:

5: float f(float x) {

6: return (sqrt(x)-x)*sin(x);

7: }

8:

9: float xmax(float a, float b, float e) {

10: _____ _, ___ = _(_), ____ = _;

11: ___ (_=_+_; _<_-_; _+=_)

12: __ ( _(_-_) < _(_) &&

13: _(_) > _(_+_) )

14: ______ _;

15: }

16:

17: int main() {

18: float a, b, e;

19: cout << "a> "; cin >> a;

20: cout << "b> "; cin >> b;

21: cout << "e> "; cin >> e;

22: cout << " < " << xmax(a, b, e) << endl;

23: }

24:

--------------------------------------------------------------------------------

[Line 9]: Where a, b, and e are floats, define xmax(a, b, e) as follows:

[Line 10]: Let max <- f(a), xmax <- a.

[Line 11]: For float x in the range [a+e, b-e) in increments of e:

[Line 12]: If f(x-e) < f(x) > f(x+e):

[Line 13]: Return x.

--------------------------------------------------------------------------------

--------------------------------------------------------------------------------

[Code 1-1-1]: c++/searching/find-substring.cpp

--------------------------------------------------------------------------------

1: #include <iostream>

2: using namespace std;

3:

4: int find(string needle, string haystack) {

5: ____ _____;

6: ___ (___ _=0; _<________.____(); _++) {

7: _____ = ____;

8: __ (________.____()-_<______.____())

9: ______ -1;

10: ___ (___ _=0; _<______.____(); _++)

11: __ (________[_+_] != ______[_])

12: _____ = _____;

13: __ (_____) ______ _;

14: }

15: ______ -1;

16: }

17:

18: int main() {

19: cout << find("pill", "caterpillar") << endl;

20: }

21:

--------------------------------------------------------------------------------

[Line 3]: Where n is the size of haystack, and m is the size of needle, and

found is a boolean,

[Line 4]: Define find(needle, haystack) as follows:

[Line 5]:

[Line 6]: For integer i in the range [0, n):

[Line 7]: Let found <- true.

[Line 8]: If (n-i>m):

[Line 9]: Return -1.

[Line 10]: For integer j in the range [0, m):

[Line 11]: If haystack[i+j] != needle[j]:

[Line 12]: Let found <- false.

[Line 13]: If found:

[Line 14]: Return i.

[Line 15]: Return -1.

--------------------------------------------------------------------------------

Any help would be appreciated

Any help would be appreciated